Wie diesen Baum/Graph

Question

Ich muss iterieren einen Baum/Grafik iterieren und eine bestimmte Ausgabe zu erzeugen, aber einige Regeln folgende:

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

Die erwartete ausgegeben werden soll (um irrelevant):

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

die Regeln sind:

1. die Spitze des Baumes 'bde' (leftmost_root_children + root + rightmost_root_children) immer vorhanden sein sollten
2. Die Reihenfolge von links nach rechts sollte beibehalten werden, z. B. sind die Kombinationen "cb" oder "gf" nicht zulässig.
3. Alle Pfade folgen der Richtung von links nach rechts.

Ich muss alle Pfade finden, die diesen Regeln folgen. Leider habe ich keinen CS Hintergrund und mein Kopf explodiert. Jeder Tipp wird hilfreich sein.

EDIT: Diese Struktur stellt meinen Baum sehr eng:

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', [], [])], 
         [])]) 

oder besser lesbar sein:

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

Answer 1

So kann diese als eine Kombination von zwei Problemen behandelt werden. Mein Code unten wird annehmen, dass die N Klasse und tree Struktur bereits wie in Ihrer Problemstellung definiert wurden.

Zuerst: Bei einer Baumstruktur wie Ihrer, wie erzeugen Sie eine In-Order-Traversierung seiner Knoten? Dies ist ein ziemlich einfaches Problem, so dass ich nur einen einfachen rekursive Generator zeige, dass es löst:

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'] 

Zweitens: Nachdem wir nun die „richtige“ Reihenfolge der Knoten haben, wir Figur neben brauchen aus alle möglichen Kombinationen davon, dass a) diese Reihenfolge zu halten, und b) enthalten die drei "Anker" -Elemente ('b', 'd', 'e'). Dies können wir mit Hilfe der immer verfügbaren itertools Bibliothek erreichen.

Die grundlegenden Schritte sind:

• die Ankerelemente identifizieren und die Liste in vier Stücke um sie herum
• Auszufinden alle Kombinationen von Elementen für jede Partition partitioniert (dh der Leistungssatz)
• Nehmen das Produkt aller solcher Kombinationen

Wie 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']