4

Possible Duplicate:
How can I create cartesian product of vector of vectors?

I'm having some logical issues figuring out how to generate all combinations of elements in a 2d vector. Here, I create a 2D vector. Neither dimension's size can be assumed.

#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'd like to output 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 am having trouble how to conceptualize the loop structure to do this properly, where the size 'array' and the elements in each sub-array is unknown/dynamic.

EDIT 1: Can't assume there are 3 arrays. There are array.size() of them ;)

Community
  • 1
  • 1
gnychis
  • 7,289
  • 18
  • 75
  • 113
  • I can probably help you, but please explain more [mathematically](http://www.mathsisfun.com/combinatorics/combinations-permutations.html) what you actually mean. – Kos Dec 23 '11 at 20:24
  • Is it perhaps a carthesian product? For 5 arrays ABCDE as input, would you expect all possible 5-tuples (abcde) where a is from A, b is from B etc? – Kos Dec 23 '11 at 20:25

2 Answers2

6

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 with i = 0 and an empty accum.

Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
2

You have three arrays, right? Size of each one of them is different, and you want all the combinations. If so this should help 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 re-write it to C++ code

EDIT: This should work for any number of arrays

The first for is just printing and the second for moving the indexes of arrays (cares about 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!

SlavaNov
  • 2,447
  • 1
  • 18
  • 26