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?

---

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

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: 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

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.

Result

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