I can not write a working algorithm for finding all possible products of array elements. That is, for example, we have an array of n elements. It is required to find the product of any pairs of elements, any triples, and so on, before the products of all elements.

Closed due to the fact that the question is too common for participants Vlad from Moscow , user194374, αλεχολυτ , AK ♦ , Ruslan_K January 20, 17 at 7:45 .

Please correct the question so that it describes the specific problem with sufficient detail to determine the appropriate answer. Do not ask a few questions at once. See “How to ask a good question?” For clarification. If the question can be reformulated according to the rules set out in the certificate , edit it .

  • The question is not related to C ++. This is a question about algorithms. - Vlad from Moscow
  • that's just what is n? because the number of products will be 2 ^ n and for n> 20 the code will work long. - pavel
  • this is placement from n to k, where each time k ++ to n - Senior Pomidor
  • 2
    "I can not write" - a statement of fact, not a question :) See "Generation of all tuples" in the 4th volume of "The Art of Programming" Knut. - Harry
  • @SeniorAutomator And what, multiplication is no longer a commutative operation? - Harry

2 answers 2

#include <bits/stdc++.h> using namespace std; int main() { vector<int> count = {10,15,30,100}; vector<int> res; res.reserve(1 << count.size()); res.push_back(1); for (unsigned int mask = 1; mask < (1 << count.size()); mask++) res.push_back ( res[ mask & (mask - 1) ] * count [ __builtin_ctz(mask) ] ); for (int x: res) cout << x<< " "; return 0; }

Like this ...

At the request of @VladD - style generator (without additional memory)

 #include <bits/stdc++.h> using namespace std; int main() { vector<int> count = {10,15,30,100}; for (unsigned __int128 mask = 0; mask < (1 << count.size()); mask++){ unsigned long long res = 1; __int128 tm = mask; for ( ; tm ; tm &= (tm - 1) ) res *= count [ __builtin_ctz(tm) ]; cout << res<<" "; } return 0; }
  • And for an array of 100 elements? :) Yes, I know how much time it will work, but it's a matter of principle! - Harry

Found it here, once wrote the Gray code generator. Since it works for this task as well, this is not the most efficient, of course, but the solution :) Just if there is no zero value in the array, then at each next step a new work can be calculated only by one division or multiplication, without going through all the elements of the array.

 #include <vector> #include <string> #include <iostream> #include <iomanip> using namespace std; class Gray { public: Gray(int N):N(N),a(N+1,false),last_(-1){} ~Gray() = default; Gray(const Gray&) = default; Gray(Gray&&) = default; Gray& operator=(const Gray&) = default; Gray& operator=(Gray&&) = default; size_t size() const { return N; } void reset(size_t newN = 0) { if (newN) N = newN; vector<bool> b(N+1,false); std::swap(a,b); last_ = -1; } bool operator[](size_t idx) const { return a[idx]; } int last() const { return last_; } bool next() { size_t j; if (!a[N]) j = 0; else { for(j = 0; j < N; ++j) if (a[j]) break; ++j; } if (j == N) return false; a[N] = !a[N]; a[j] = !a[j]; last_ = j; return true; } private: vector<bool> a; size_t N; int last_; }; int main(int argc, const char * argv[]) { int m[] = { 2, 3, 5, 7 }; Gray g(sizeof(m)/sizeof(m[0])); do { if (g.last() >= 0) { int p = 1; for(size_t i = 0; i < g.size(); ++i) if (g[i]) p *= m[i]; cout << setw(6) << p << " = "; for(size_t i = 0, first = 1; i < g.size(); ++i) if (g[i]) { if (!first) { cout << " * "; } else { first = 0; } cout << m[i]; } cout << "\n"; } } while(g.next()); // Только произведения - если нет нулевого элемента. g.reset(); int p = 1; do { if (g.last() >= 0) { if (g[g.last()]) p *= m[g.last()]; else p /= m[g.last()]; cout << setw(6) << p <<"\n"; } } while(g.next()); }