How to iterate this tree/graph

Question

I need to iterate a tree/graph and produce a certain output but following some rules:

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

The expected output should be (order irrelevant):

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

The rules are:

1. The top of the tree 'bde' (leftmost_root_children+root+rightmost_root_children) should always be present
2. The left-right order should be preserved so for example the combinations 'cb' or 'gf' are not allowed.
3. All paths follow the left to right direction.

I need to find all paths following these rules. Unfortunately I don't have a CS background and my head is exploding. Any tip will be helpful.

EDIT: This structure represents my tree very 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 be more readable:

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

Answer 1

So this can be treated as a combination of two problems. My code below will assume the N class and tree structure have already been defined as in your problem statement.

First: given a tree structure like yours, how do you produce an in-order traversal of its nodes? This is a pretty straightforward problem, so I'll just show a simple recursive generator that solves it:

def inorder(node):
    if not isinstance(node, list):
        node = [node]
    for n in node:
        for left in inorder(getattr(n, 'lefts', [])):
            yield left
        yield n.name
        for right in inorder(getattr(n, 'rights', [])):
            yield right

print list(inorder(tree))
# ['a', 'b', 'c', 'd', 'f', 'g', 'e']

Second: Now that we have the "correct" ordering of the nodes, we next need to figure out all possible combinations of these that a) maintain this order, and b) contain the three "anchor" elements ('b', 'd', 'e'). This we can accomplish using some help from the always-handy itertools library.

The basic steps are:

• Identify the anchor elements and partition the list into four pieces around them
• Figure out all combinations of elements for each partition (i.e. the power set)
• Take the product of all such combinations

Like so:

from itertools import chain, combinations
# powerset recipe taken from 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) for 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) for 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) for x in parts]
    for 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']