StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h1>Algorithms</h1> <h2>1: Going from the input</h2> <p>So if you have the lists <code>[1, 2, 3]</code>, <code>[4, 5, 6]</code>, <code>[7, 8, 9]</code> you have <a href="http://paste.ubuntu.com/706117/" rel="nofollow noreferrer">this list of possible permutiations</a></p> <p>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 <code>1</code>, then move on to a <code>4</code> and then find a <code>7</code> at the third level. If I do not, I have to add this there.</p> <pre><code>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() </code></pre> <h2>2: Back to the original lists</h2> <p>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:</p> <pre><code>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 </code></pre> <p>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.</p> <h1>Result</h1> <p>This is the tree I get, 0 is the artificial root. The nodes are "recycled" since they all bear the same content. (Made with <a href="http://www.graphviz.org/" rel="nofollow noreferrer">dot</a>.)</p> <p><a href="http://wstaw.org/m/2011/10/11/tree.png" rel="nofollow noreferrer">http://wstaw.org/m/2011/10/11/tree.png</a></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload