1# Generate all possible single-root message thread structures of size 2# argv[1]. Each output line is a thread structure, where the n'th 3# field is either a number giving the parent of message n or "None" 4# for the root. 5import sys 6from itertools import chain, combinations 7 8def subsets(s): 9 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) 10 11nodes = set(range(int(sys.argv[1]))) 12 13# Queue of (tree, free, to_expand) where tree is a {node: parent} 14# dictionary, free is a set of unattached nodes, and to_expand is 15# itself a queue of nodes in the tree that need to be expanded. 16# The queue starts with all single-node trees. 17queue = [({root: None}, nodes - {root}, (root,)) for root in nodes] 18 19# Process queue 20while queue: 21 tree, free, to_expand = queue.pop() 22 23 if len(to_expand) == 0: 24 # Only print full-sized trees 25 if len(free) == 0: 26 print(" ".join(map(str, [msg[1] for msg in sorted(tree.items())]))) 27 else: 28 # Expand node to_expand[0] with each possible set of children 29 for children in subsets(free): 30 ntree = {child: to_expand[0] for child in children} 31 ntree.update(tree) 32 nfree = free.difference(children) 33 queue.append((ntree, nfree, to_expand[1:] + tuple(children))) 34