如何从多棵树中获取所有组合？

Question

除了使用 x 嵌套 for 循环之外，我不知道如何从 x 组数据中获取所有可能性，我不想这样做，因为我不知道 x 的值，这使得 for 循环的数量变得非常可能硬编码不等于所需的循环数。

假设我有：

A:1,2,3,4
B:2,4,65,2
C:1,3,2
D:2,8

并且我想从每个组中获取 1 个项目的所有组合（在我的代码中，我使用 std::vector），我该怎么做？有人可以发布一个我可以遵循的通用伪代码来执行此操作吗？

Answer 1

如果您不知道自己有多少个“组”，我假设您至少拥有所有这些组的一些集合？即，所有向量的数组/向量？

如果是这样，这里有一个大概的想法，

void iterateAllCombinations(array_of_groups, current_group_index,temp_result,callback_function)
{
  current_group = array_of_groups[current_group_index]
  for each element in current_group
  {
    temp_result[current_group_index]=element
    if current_group_index>0
      iterateAllCombinations(array_of_groups,current_group_index-1,temp_result,callback_function)
    else
      callback_function(temp_result)
  }
}

this would be called in some fashion like:
iterateAllCombinations(my_groups,my_groups.length-1,new vector[my_groups.length],&do_something_with_array)

对正在发生的事情的基本解释：
当您调用该函数时，它将开始遍历“顶部”组中的每一项（组数组中的最后一项）。如果除了“顶部”组之外还有更多组，它将调用相同的函数，传递到目前为止的当前项目，并告诉它查看下一组。

下一个级别将开始检查每个项目，并以相同的方式运行。这个过程一直持续到你到达底部组，在那里，它不会调用另一个级别，而是将所有结果的集合传递给你的回调函数，回调函数将使用它们。

当底层遍历完所有项目后，它将返回到上一层，仍处于“foreach”循环中。上一层会转到下一项，并调用底层，从头开始。这样一直持续下去，直到最终“最高”级别也完成了每个项目。

---

这是伪代码，具体内容根据您的语言而变化。
“临时结果”可以是声明和分配的预先数组（就像我在伪代码中所示），也可以是在每次递归调用之前压入并在之后弹出的堆栈，也可以是数组/您在每次递归调用之前复制并附加的向量。您甚至可以有一个链表，每个节点都存储在该函数调用的堆栈帧中，并且您只需将“父级”的指针传递到下一级。

如果您想要做一件特定的事情，您可以将“callback_function”替换为该特定的事情。或者，如果您的语言允许，您可以使用它作为迭代器/生成器，并让“回调”是隐式的。

如果您真的讨厌递归代码，您可以编写与 while 循环相同的东西，但它更直接将其写为递归函数。