python - How to iterate this tree/graph -

i need iterate tree/graph , produce output following rules:

     _ d    /  / \   b  c  _e  /     / |     f  g 

the expected output should (order irrelevant):

{'bde', 'bcde', 'abde', 'abcde', 'bdfe', 'bdfge', 'abdfe', ...} 

the rules are:

1. the top of tree 'bde' (leftmost_root_children+root+rightmost_root_children) should present
2. the left-right order should preserved example combinations 'cb' or 'gf' not allowed.
3. all paths follow left right direction.

i need find paths following these rules. unfortunately don't have cs background , head exploding. tip helpful.

edit: structure represents tree closely:

class n():     """node"""     def __init__(self, name, lefts, rights):         self.name = name         self.lefts = lefts         self.rights = rights  tree = n('d', [n('b', [n('a', [], [])], []), n('c', [], [])],                [n('e', [n('f', [], []), n('g', [], [])],                        [])]) 

or may more readable:

n('d', lefts =[n('b', lefts=[n('a', [], [])], rights=[]), n('c', [], [])],         rights=[n('e', lefts=[n('f', [], []), n('g', [], [])], rights=[])]) 

so can treated combination of 2 problems. code below assume n class , tree structure have been defined in problem statement.

first: given tree structure yours, how produce in-order traversal of nodes? pretty straightforward problem, i'll show simple recursive generator solves it:

def inorder(node):     if not isinstance(node, list):         node = [node]     n in node:         left in inorder(getattr(n, 'lefts', [])):             yield left         yield n.name         right in inorder(getattr(n, 'rights', [])):             yield right  print list(inorder(tree)) # ['a', 'b', 'c', 'd', 'f', 'g', 'e'] 

second: have "correct" ordering of nodes, next need figure out possible combinations of these a) maintain order, , b) contain 3 "anchor" elements ('b', 'd', 'e'). can accomplish using always-handy itertools library.

the basic steps are:

• identify anchor elements , partition list 4 pieces around them
• figure out combinations of elements each partition (i.e. power set)
• take product of such combinations

like so:

from itertools import chain, combinations # powerset recipe taken itertools documentation def powerset(iterable):     "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"     s = list(iterable)     return chain.from_iterable(combinations(s, r) r in range(len(s)+1))  def traversals(tree):     left, mid, right = tree.lefts[0].name, tree.name, tree.rights[0].name     nodes = list(inorder(tree))     l_i, m_i, r_i = [nodes.index(x) x in (left, mid, right)]     parts = nodes[:l_i], nodes[l_i+1:m_i], nodes[m_i+1:r_i], nodes[r_i+1:]     psets = [powerset(x) x in parts]     p1, p2, p3, p4 in product(*psets):         yield ''.join(chain(p1, left, p2, mid, p3, right, p4))  print list(traversals(tree)) # ['bde', 'bdfe', 'bdge', 'bdfge', 'bcde', 'bcdfe',  #  'bcdge', 'bcdfge', 'abde', 'abdfe', 'abdge', 'abdfge',  #  'abcde', 'abcdfe', 'abcdge', 'abcdfge']