c++ - 二维 vector 中元素的所有排列(笛卡尔积)

Question

这是我一直坚持的一小部分，它是更大任务的一部分。

我有一个二维 vector ，例如:

v1: 0 1 2 3 4  
v2: 0 1 2  
v3: 0 1 2 3 4  
v4: 0 1 2 3  
v5: 0 1 2 3 4  

(每一行是一个 vector )

我需要找到所有排列，从每一行中选择一个元素。正如有人指出的那样，这将是笛卡尔积。
我试过使用循环，但这只会在一个方向上起作用(它错过了很多排列)
我也研究了 next_permutation，但我不确定是否可以将其应用于 2D vector 。

此外，行数不是静态的，所以我不能嵌套 5 个循环，因为根据条件可能会有更多或更少的行。

有办法吗？

Answer 1

我将只写出一个可能的答案，效率不是很高，但应该有用。

请注意，我假设(在您的示例中)您想要所有 5 元素组，第一个元素取自 v1，第二个元素取自 v2，第三个元素取自 v3，等等。

void gen_all (
    vector<vector<int> > & output_perms,
    vector<vector<int> > const & input,
    vector<int> & cur_perm,
    unsigned cur_row = 0
)
{
  if (cur_row >= input.size())
  {
    // This is where you have found a new permutation.
    // Do whatever you want with it.
    output_perms.push_back (cur_perm);
    return;
  }

  for (unsigned i = 0; i < input[cur_row].size(); ++i)
  {
    cur_perm.push_back (input[cur_row][i]);
    gen_all (output_perms, input, cur_perm, cur_row + 1);
    cur_perm.pop_back ();
  }
}

像这样调用上面的函数:(假设 v 保存你的原始集合。)

vector<vector<int> > output;
vector<int> temp;
gen_all (output, v, temp);

正如我之前所说，有更高效和优雅的方法，上面的代码甚至可能无法编译(我只是写在这里。)