Creating a tree from a list of item combinations

Question

I have n lists A, B, C ... which contain a, b, c ... elements. I use them to create lists of possible combinations (list of lists), so the first item is taken from table A, the second from B, etc. What is the best way to convert this flat structure to a tree, followed by the root of the elements of list A, each of which has all the elements of list B, etc., thereby creating every possible combination in the form of a path from the root?

Answer 1

Algorithms

1: transition from input

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

So now I will look at the lists and their elements. All are the paths of the tree you want. Therefore, if everything were placed in a tree, I could find node 1 , and then go to 4 , and then find 7 on the third level. If I do not, I must add this.

 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: Return to the original lists

If the tree is equally symmetrical, you can simply slice the levels of the trees, giving you a list of A, B and C. Then you go back to the square and you can build 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 list heap (a, b, c) and stores unique elements in the list. Then it has lists A, B, C and generates a tree from it.

Result

This is the tree that I get, 0 is the artificial root. Nodes are “redesigned” because they all have the same content. (Made with a dot .)

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