从项目组合列表创建树

Question

我有 n 个列表 A,B,C... 其中包含 a,b,c... 元素。我使用它们创建可能组合的列表（列表列表），这样第一个元素取自表 A，第二个元素取自 B 等。将这种平面结构转换为根跟随的树的最佳方法是什么由列表 A 的元素组成，每个元素都具有列表 B 的所有元素等。从而以从根开始的路径形式创建每种可能的组合？

Answer 1

算法

1：从输入开始

因此，如果您有列表 [1, 2, 3]、[4, 5, 6]、[7, 8 , 9] 你有这个可能的排列列表

所以我现在会浏览列表及其元素。所有代表你想要的树的路径。因此，如果所有内容都放入树中，我将能够找到节点 1，然后移动到 4，然后找到 7 > 在第三级。如果我不这样做，我必须在那里添加它。

paths = [
    [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 6, 7], [1, 6, 8], [1, 6, 9], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 6, 7], [2, 6, 8], [2, 6, 9], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 6, 7], [3, 6, 8], [3, 6, 9]
]

class Tree(object):
    def __init__(self, node=None):
        self.node = node
        self.children = []

    def addChild(self, child):
        self.children.append(child)

    def toList(self):
        if len(self.children) > 0:
            return [self.node, [x.toList() for x in self.children]]
        else:
            return [self.node]

tree = Tree()

# iterate through the lists
for path in paths:
    subtree = tree

    for value in path:
        # check whether the current value already exists at this position in the tree
        found = False
        for child in subtree.children:
            if value == child.node:
                subtree = child
                found = True
                break

        # attach the leaf to the current position in the tree if needed
        if not found:
            newchild = Tree(node=value)
            subtree.addChild(newchild)
            subtree = newchild

        # use the found or created leaf as a position for the next value in the path-list

print tree.toList()

2：回到原始列表

如果树像看起来一样对称，您也可以只对树的级别进行切片，得到列表 A、B 和 C。然后，您回到第一个方并可以构建树：

paths = [
    [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 6, 7], [1, 6, 8], [1, 6, 9], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 6, 7], [2, 6, 8], [2, 6, 9], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 6, 7], [3, 6, 8], [3, 6, 9]
]

lists = [[]]*len(paths[0])
for i in xrange(len(paths[0])):
    lists[i] = set([])
    for l in paths:
        lists[i].add(l[i])

def iterate(listnumber):
    result = []
    for element in lists[listnumber]:
        if listnumber < len(lists)-1:
            result.append([element, iterate(listnumber+1)])
        else:
            result.append([element])
    return result

tree = iterate(0)

print tree

它遍历列表堆（a、b、c）的每一层，并将唯一成员存储在列表中。然后它有列表 A、B、C 并从中生成树。

结果

这是我得到的树，0是人工根。这些节点被“回收”，因为它们都具有相同的内容。 （使用 dot 制作。）

http://wstaw.org/m/2011/10/11/tree.png