Generate all combination of elements in 2d vector

Question

Possible duplicate:
How to create a cartesian product of vector vectors?

I am having some logical problems that determine how to create all combinations of elements in a 2d vector. Here I am creating a 2D vector. No size size can be accepted.

#include <iostream> #include <vector> using namespace std; int main() { srand(time(NULL)); vector< vector<int> > array; // This creates the following: // array[0]: {0, 1, 2} // array[1]: {3, 4, 5, 9} // array[2]: {6, 7, 8} for(int i=0; i<3; i++) { vector<int> tmp; tmp.push_back((i*3)+0); tmp.push_back((i*3)+1); tmp.push_back((i*3)+2); if(i==1) tmp.push_back((i*3)+6); array.push_back(tmp); } } 

After creating the vector, I would like to display all possible combinations as follows:

  comb[0] = {0, 3, 6} comb[1] = {0, 3, 7} comb[2] = {0, 3, 8} comb[3] = {0, 4, 6} comb[4] = {0, 4, 7} comb[x] = {...} 

However, I had problems with the concept of the loop structure in order to do it right, where the size is “array” and the elements in each submatrix are unknown / dynamic.

EDIT 1: It cannot be assumed that there are 3 arrays. Of these, array.size () :)

Answer 1

The easiest way for unknown sizes is recursion.

 void combinations(vector<vector<int> > array, int i, vector<int> accum) { if (i == array.size()) // done, no more rows { comb.push_back(accum); // assuming comb is global } else { vector<int> row = array[i]; for(int j = 0; j < row.size(); ++j) { vector<int> tmp(accum); tmp.push_back(row[j]); combinations(array,i+1,tmp); } } } 

Initially, call using i = 0 and an empty accum .

Answer 2

You have three arrays, right? The size of each of them is different, and you need all the combinations. If this helps you:

Pseudo Code:

 for(i=0; i<size(array0), i++) { for(j=0; j<size(array1), j++) { for(k=0; k<size(array2), k++) { print("{array0[i], array1[j], array2[k]} \n"); } } } 

I hope you can rewrite it in C ++ code

EDIT: This should work for any number of arrays

The first for only prints, and the second for moves the indexes of the arrays (takes care of overflow)

Pseudo code again:

 comb = 0; stop = false; while(!stop) { output("Combination["+comb+"] = {"); for(i = 0; i < num_of_arrays; i++) { index = index_array[i]; output(array[i][index]); // assume this function takes care about right formatting } output("}\n"); index_array[num_of_arrays-1]++; for(i = num_of_arrays-1; i >= 0; i--) { index = index_array[i] if(index == size(array[i]) { if(i == 0) stop = true; else { index_array[i] = 0; index_array[i-1]++; } } } comb++; } 

Hope this helps!