查找树的所有值分配，其中每个节点的路径都具有唯一元素

Question

我有一棵树，我需要为每个节点分配一个值，以便对于每个节点，从该节点到根的路径没有重复值。我正在尝试为一组树生成所有值分配并存储它们。我一直无法计算出或找到一个像样的算法来顺序生成这些树。任何方向或想法将不胜感激。

Answer 1

你可以使用这个算法：

从 [1...m] 的根和数组作为选项数组开始。
对于每个选项：选择一个并分配给 root
在所有子项上删除该选项后调用递归

也许这段伪代码会更好地解释它：

function assign(root, options) {
    for each options as option:
        assign root with option
        newOptions = options - option // remove newly assign value
        for each root->childs as child:
            call assign(child, newOptions) //recursive call after removing current option
} 

options = [1...m]
assign(root, options)

这比蛮力方法更复杂

希望有所帮助！

查找树的所有值分配，其中每个节点的路径都具有唯一元素

Finding all value assignments to tree where paths to each node have unique elements

tree

graph-theory

graph-algorithm