algorithm - 构建一棵没有重复值的k叉树

Question

假设我有两个值:x1 和 x2。

给定一个根，如何使用 k-ary 树构建 x1 和 x2 的所有组合？

例子:

#0    root
      /   \
#1  x1     x2
     |
#2  x2

在 #1 层，我有初始元素 x1 和 x2。

在级别 #2 我有 x2，组合 x1x2，但没有 x1因为这将是一个重复组合(x2x1，我们不关心这里的元素顺序)。

如果我有两个以上的元素，树会继续下去，直到层数等于元素数减 1。

我已经构建了初始 #1 关卡。但是如何在不重复组合的情况下继续生成树呢？换句话说，如何以最有效的方式验证我是否应该将给定元素放在树上。有一些著名的算法吗？

附加信息:PHP

Answer 1

编辑:构建树的一些修改

我的想法是拥有一个包含 n 个元素的 n 叉树 (x1, x2,... ,xn) .让根成为x0 ，然后对于任何节点 xi (0 <= i <= n) , 你应该有所有 child xj其中 (i < j <= n) .这样你就可以拥有所有不重复的组合。例如。对于 n=3，三元树将是这样的:

root ---> x1 ---> x2 ---> x3
          |  ---> x3
root ---> x2 ---> x3
root ---> x3