How can I create cartesian product of vector of vectors?

Question

I've a vector of vectors say vector<vector<int> > items of different sizes like as follows

1,2,3 4,5 6,7,8 

I want to create combinations in terms of Cartesian product of these vectors like

1,4,6 1,4,7 1,4,8 and so on till 3,5,8 

How can I do that ? I've looked up several links and I've also listed them at the end of this post but I'm not able to interpret that as I'm not that familiar with the language. Could some body help me with this.

#include <iostream> #include <iomanip> #include <vector>  using namespace std;  int main() {     vector<vector<int> > items;     int k = 0;      for ( int i = 0; i < 5; i++ ) {         items.push_back ( vector<int>() );          for ( int j = 0; j < 5; j++ )             items[i].push_back ( k++ );     }      cartesian ( items ); // I want some function here to do this. } 

This program has equal length vectors and I put this so that it will be easier to understand my data structure. It will be very helpful even if somebody uses others answers from other links and integrate with this to get the result. Thank you very much

Couple of links I looked at one Two Program from : program

Answer 1

First, I'll show you a recursive version.

// Cartesion product of vector of vectors  #include <vector> #include <iostream> #include <iterator>  // Types to hold vector-of-ints (Vi) and vector-of-vector-of-ints (Vvi) typedef std::vector<int> Vi; typedef std::vector<Vi> Vvi;  // Just for the sample -- populate the intput data set Vvi build_input() {    Vvi vvi;     for(int i = 0; i < 3; i++) {       Vi vi;       for(int j = 0; j < 3; j++) {          vi.push_back(i*10+j);       }       vvi.push_back(vi);    }    return vvi; }  // just for the sample -- print the data sets std::ostream& operator<<(std::ostream& os, const Vi& vi) {   os << "(";   std::copy(vi.begin(), vi.end(), std::ostream_iterator<int>(os, ", "));   os << ")";   return os; } std::ostream& operator<<(std::ostream& os, const Vvi& vvi) {   os << "(\n";   for(Vvi::const_iterator it = vvi.begin();       it != vvi.end();       it++) {       os << "  " << *it << "\n";   }   os << ")";   return os; }  // recursive algorithm to to produce cart. prod. // At any given moment, "me" points to some Vi in the middle of the // input data set.  //   for int i in *me: //      add i to current result //      recurse on next "me" //  void cart_product(     Vvi& rvvi,  // final result     Vi&  rvi,   // current result      Vvi::const_iterator me, // current input     Vvi::const_iterator end) // final input {     if(me == end) {         // terminal condition of the recursion. We no longer have         // any input vectors to manipulate. Add the current result (rvi)         // to the total set of results (rvvvi).         rvvi.push_back(rvi);         return;     }      // need an easy name for my vector-of-ints     const Vi& mevi = *me;     for(Vi::const_iterator it = mevi.begin();         it != mevi.end();         it++) {         // final rvi will look like "a, b, c, ME, d, e, f"         // At the moment, rvi already has "a, b, c"         rvi.push_back(*it);  // add ME         cart_product(rvvi, rvi, me+1, end); add "d, e, f"         rvi.pop_back(); // clean ME off for next round     } }  // sample only, to drive the cart_product routine. int main() {   Vvi input(build_input());   std::cout << input << "\n";    Vvi output;   Vi outputTemp;   cart_product(output, outputTemp, input.begin(), input.end());   std::cout << output << "\n"; } 

Now, I'll show you the recursive iterative version that I shamelessly stole from @John :

The rest of the program is pretty much the same, only showing the cart_product function.

// Seems like you'd want a vector of iterators // which iterate over your individual vector<int>s. struct Digits {     Vi::const_iterator begin;     Vi::const_iterator end;     Vi::const_iterator me; }; typedef std::vector<Digits> Vd; void cart_product(     Vvi& out,  // final result     Vvi& in)  // final result  {     Vd vd;      // Start all of the iterators at the beginning.     for(Vvi::const_iterator it = in.begin();         it != in.end();         ++it) {         Digits d = {(*it).begin(), (*it).end(), (*it).begin()};         vd.push_back(d);     }       while(1) {          // Construct your first product vector by pulling          // out the element of each vector via the iterator.         Vi result;         for(Vd::const_iterator it = vd.begin();             it != vd.end();             it++) {             result.push_back(*(it->me));         }         out.push_back(result);          // Increment the rightmost one, and repeat.          // When you reach the end, reset that one to the beginning and         // increment the next-to-last one. You can get the "next-to-last"         // iterator by pulling it out of the neighboring element in your         // vector of iterators.         for(Vd::iterator it = vd.begin(); ; ) {             // okay, I started at the left instead. sue me             ++(it->me);             if(it->me == it->end) {                 if(it+1 == vd.end()) {                     // I'm the last digit, and I'm about to roll                     return;                 } else {                     // cascade                     it->me = it->begin;                     ++it;                 }             } else {                 // normal                 break;             }         }     } } 

Answer 2

Here is a solution in C++11.

The indexing of the variable-sized arrays can be done eloquently with modular arithmetic.

The total number of lines in the output is the product of the sizes of the input vectors. That is:

N = v[0].size() * v[1].size() * v[2].size() 

Therefore the main loop has n as the iteration variable, from 0 to N-1. In principle, each value of n encodes enough information to extract each of the indices of v for that iteration. This is done in a subloop using repeated modular arithmetic:

#include <cstdlib> #include <iostream> #include <numeric> #include <vector> using namespace std;  void cartesian( vector<vector<int> >& v ) {   auto product = []( long long a, vector<int>& b ) { return a*b.size(); };   const long long N = accumulate( v.begin(), v.end(), 1LL, product );   vector<int> u(v.size());   for( long long n=0 ; n<N ; ++n ) {     lldiv_t q { n, 0 };     for( long long i=v.size()-1 ; 0<=i ; --i ) {       q = div( q.quot, v[i].size() );       u[i] = v[i][q.rem];     }     // Do what you want here with u.     for( int x : u ) cout << x << ' ';     cout << '\n';   } }  int main() {   vector<vector<int> > v { { 1, 2, 3 },                            { 4, 5 },                            { 6, 7, 8 } };   cartesian(v);   return 0; } 

Output:

1 4 6  1 4 7  1 4 8  ... 3 5 8