生成二维向量中所有元素的组合

Question

可能重复：
如何创建向量向量的笛卡尔积？ 我有一些逻辑问题，无法确定如何生成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()确定;)

- gnychis

---

我可能可以帮助你，但请用数学的方式更详细地解释你的意思。 - Kos

这可能是笛卡尔积吗？对于输入的5个数组ABCDE，您是否期望所有可能的5元组（abcde），其中a来自A，b来自B等等？ - Kos

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为空。

- Daniel Fischer

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

希望这能帮到你！

- SlavaNov

---

所以这个技巧/挑战在于我不能假设只有3个数组，否则我完全同意你的解决方案。 - gnychis

修改后请查看代码。 - SlavaNov

index_array[]是什么，它如何初始化？ - gnychis

index_array - 计数器数组（你正在运行的数组索引）- 初始化为0 - SlavaNov