生成元素的所有组合中的2D矢量

Question

可能重复：
How can I create cartesian product of vector of vectors?

我在搞清楚如何产生二维向量元素的所有组合逻辑的一些问题。在这里，我创建了一个2D矢量。尺寸的大小都不能被假定。

#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); 
    } 
} 

创建矢量之后，我想输出所有可能的组合如下：

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] = {...} 

不过，我有麻烦如何概念化循环结构正确，在执行此操作大小'数组'，每个子数组中的元素是未知/动态的。编辑1：不能假设有3个数组。它们有array.size（）;）

Answer 1

未知大小的最简单方法是递归。

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); 
     } 
    } 
} 

与i = 0和空accum最初叫。

Answer 2

你有三个数组，对吧？他们每个人的大小是不同的，你想要所有的组合。如果是的话这应该可以帮助您：

伪代码：

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"); 

     } 
    } 
} 

我希望你可以把它重新写C++代码

编辑：这应该为任何数量的阵列

的工作

第一个for只是打印而第二个for移动阵列的索引（关心溢出）

伪代码再次：​​

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++; 
} 

希望这有助于！