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

我不知道如何从x组数据中获得所有可能性，而不是使用x嵌套for循环，我不想这样做，因为我不知道x的值，这使得它非常可能的数量for循环硬编码不等于所需循环的数目。如何从多个树中获取所有组合？

说我有：

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

，我想从每个组1项的每一个组合（在我的代码，使用std::vector <myclass> IM），会怎么做呢？有人可以发布一个一般的伪代码，我可以按照这样做吗？

来源

2011-03-17 treehugger

命令是否重要？我的意思是它是排列还是组合？因为你的问题说“从每个组获得1个项目的每个组合” – 2011-03-17 02:11:05

组合。我的错。我总是得到那些2困惑 – treehugger 2011-03-17 02:25:41

如果你不知道你有多少'组'，我想你至少有一些它们的集合？即所有矢量的数组/矢量？

如果是这样，这里有什么工作

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)

发生了什么事情的基本解释一个总体思路：当你调用该函数，它将开始通过每一个项目上的“顶”组会（array_of_groups中的最后一个）。如果除了“顶级”组之外还有更多组，它会调用相同的功能，传递当前的项目，并告诉它看下一组。

这下一个级别将开始贯穿每个项目，并行为相同的方式。这一直持续到你到底层组，在那里，而不是调用另一个层次，它将所有结果的集合传递给你的回调函数，这个函数将使用它们。

当最低级别通过所有项目时，它将返回到下一级别，它仍处于其'for each'循环中。下一级将进入下一个项目，并调用最低级别，这将从头开始。这一直持续下去，直到最终甚至是“最高”级别通过每个项目。

这就是伪代码，具体情况因您的语言而异。 'temp result'可以是一个声明和分配的前期数组（如我在伪代码中所示），或者它可以是在每次递归调用之前被推送并在之后弹出的堆栈，或者它可以是数组/ vector，在每次递归调用之前复制并追加。你甚至可以有一个链表，每个节点只存储在栈函数调用的栈帧中，而你只需要将“父”的指针传递到下一层。

如果你有一件你想要做的事情，你可以用这个特定的东西代替'callback_function'。或者，如果你的语言允许的话，你可以用它作为迭代器/生成器，并且让这个'回调'隐含起来

如果你真的讨厌递归代码，你可以写一个while循环，但它是将其作为递归函数写得更直接。

来源

2011-03-17 03:01:37 YenTheFirst

谢谢！即时通讯使用C + +和即时通讯尝试排序通过类（如在学校，而不是编程对象）时间来找出所有的可能性工作 – treehugger 2011-03-17 03:08:37

啊。那么在这种情况下，做所有的组合可能有点暴躁，而且速度很慢。如果你只是想找到一个工作时间表（或所有时间表），我敢肯定有更有效的方法。如果没有别的办法，你可能会想要检查方法的每个级别的冲突，而不仅仅是在最后，以避免*很多不必要的循环。 – YenTheFirst 2011-03-17 03:43:10

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

回答

相关问题