c++ - Every combination of X numbers possible if we select one value from each of Y vectors -

this question has answer here:

• how can create cartesian product of vector of vectors? 9 answers

if there formal name problem (or duplicate , haven't found right question at) pointing out should searching appreciated! however, haven't been able find discussion or approaches specific problem.

i'm trying keep question simple possible, if more details let me know.

say have 4 random length vectors of int:

std::vector<int> v1 {1, 7, 5, 2}; std::vector<int> v2 {4, 2, 1}; std::vector<int> v3 {1, 9, 4, 6, 4, 1, 2}; std::vector<int> v4 {9, 4}; 

out of these 4 vectors, need generate every possible combination select 1 int each source vector (v1 - v4) @ time. result should generate every possible n length number out of source vectors n = number of source vectors (4 in case).

a few of possible combinations easy generate, example selecting first number out of each source vector:

1 4 1 9 

selecting last number of each source vector:

2 1 2 4 

where i'm stuck generating every single combination possible. need every possible n length number can created combining 1 int each of 4 source vectors.

thank you!

you indeed describing cartesian product of sets. ordinary product of numbers, operation on 2 things, can applied successively on more 2 things:

a x b x c x d = x (b x (c x d))

that structure key understanding problem. can break down recursive sub-problems each involving 2 sets. way can handle arbitrary number of sets.

the program solving problem can recursive well, or can iterative. follows semi-optimized recursive solution using lists of sets represented vector<int>. given list of sets

a, ...

it calculates cartesian product of 2 things: a, , cartesian product of rest of sets:

a x (...)

you can rearrange procedure start @ base case , go upward, i.e. ((d x c) x b) x a. way can use loop rather recursive calls. thinking recursive structure of problem way organize thoughts.

void cartesian_product( list< vector<int> > sets, list< vector<int> >& product) {         if ( sets.empty() )                 return;          // first set         auto& s = sets.front();          // base case         if ( ++begin( sets ) == end( sets ) ) {                 ( auto k : s ) {                         product.push_back( { k } );                 }                 return;         }          // cartesian product of rest of sets         cartesian_product( list< vector<int> >( ++begin( sets ), end( sets ) ), product );          // make additional copies of product , append each element of first set them         list< vector<int> > additions;         ( auto k = ++begin( s ); k != end( s ); ++k ) {                 list< vector<int> > ad = product;                 ( auto& x : ad ) {                         x.push_back( *k );                 }                 additions.splice( end( additions ), ad );         }          // append first element of first set original product         ( auto& x : product ) {                 x.push_back( s.front() );         }          // append additions final product         product.splice( end( product ), additions );          return; } 

---

here's rest of program:

#include <cassert> #include <iostream> #include <list> #include <vector>  using std::vector; using std::list; using std::cout; using std::endl;  void cartesian_product( list< vector<int> > sets, list< vector<int> > &product);  int main( int argc, char *argv[] ) {         list< vector<int> > sets = {                 {1, 7, 5, 2},                 {4, 2, 1},                 {1, 9, 4, 6, 4, 1, 2},                 {9, 4}         };          list< vector<int> > product;         cartesian_product( sets, product );          ( auto& x : product ) {                 cout << "{ ";                 ( auto k : x ) {                         cout << k << " ";                 }                 cout << "}" << endl;         } }