从项目组合列表创建树 [英] Creating a tree from a list of item combinations

问题描述

我有n个列表A，B，C ...，其中包含a，b，c ...元素.我正在使用它们创建可能组合的列表(列表列表)，例如，第一个元素来自表A，第二个元素来自表B，等等.将这种扁平结构转换为遵循根的树的最佳方法是什么?通过列表A的元素，每个元素都具有列表B的所有元素等，从而以从根到路径的形式创建每种可能的组合?

I have n lists A,B,C... which contain a,b,c... elements. I'm using them to create a lists of possible combinations (list of lists), such that first element is taken from table A, second from B etc. What is the best way to transform this flat structure to a tree which root is followed by elements of list A, each having all elements of list B etc. thus creating every possible combination in a form of a path from the root?

推荐答案

算法

1:从输入开始

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

Algorithms

1: Going from the input

So if you have the lists [1, 2, 3], [4, 5, 6], [7, 8, 9] you have this list of possible permutiations

因此，我现在将遍历列表及其元素.全部代表您想要的树的路径.因此，如果所有内容都放入树中，那么我将能够找到节点1，然后移至4，然后在第三级找到7.如果我不这样做，则必须在此添加.

So I would now go through the lists and their elements. The all represent paths of the tree you want. So if everything was put into the tree, I would be able to find a node 1, then move on to a 4 and then find a 7 at the third level. If I do not, I have to add this there.

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.然后，您回到第一个平方并可以构建树:

2: Back to the original lists

If the tree is as symmetric as it seems, you could also just slice the levels of the trees, giving you the list A, B and C. Then, you are back to square one and can build up the tree:

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，并从中生成树.

It goes through each layer of the pile of lists (a, b, c) and stores the unique members in a list. Then it has the lists A, B, C and generates the tree out of it.

这是我得到的树，0是人工根.节点被回收"，因为它们都承载相同的内容. (由点制成.)

This is the tree I get, 0 is the artificial root. The nodes are "recycled" since they all bear the same content. (Made with dot.)

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

这篇关于从项目组合列表创建树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！