Come iterare questo albero/grafico

Question

ho bisogno di iterare un albero/grafico e produrre una certa uscita ma seguendo alcune regole:

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

Il risultato atteso dovrebbe essere (ordine irrilevante):

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

le regole sono:

1. la cima dell'albero 'BDE' (leftmost_root_children + radice + rightmost_root_children) devono essere sempre presenti
2. L'ordine left-right deve essere conservato, ad esempio le combinazioni 'cb' o 'gf' non sono consentite.
3. Tutti i percorsi seguono la direzione da sinistra a destra.

Devo trovare tutti i percorsi seguendo queste regole. Sfortunatamente non ho uno sfondo in CS e la mia testa sta esplodendo. Qualsiasi suggerimento sarà utile.

EDIT: Questa struttura rappresenta il mio albero molto da vicino:

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

o può essere più leggibile:

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

Answer 1

Quindi questo può essere trattata come una combinazione di due problemi. Il mio codice di seguito presupporrà che la classe N e la struttura tree siano già state definite come nell'istruzione del problema.

Primo: data una struttura ad albero come la tua, come si produce una traversata in ordine dei suoi nodi? Questo è un problema abbastanza semplice, quindi mi limiterò a mostrare un semplice generatore ricorsivo che risolve:

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

Secondo: Ora che abbiamo l'ordinamento "corretto" dei nodi, abbiamo accanto bisogno di figura tutte le possibili combinazioni di questi che a) mantengono questo ordine e b) contengono i tre elementi "di ancoraggio" ('b', 'd', 'e'). Questo è possibile ottenere utilizzando l'aiuto della sempre pratica libreria itertools.

I passi fondamentali sono:

• Identificare gli elementi di ancoraggio e suddividere l'elenco in quattro parti che li circondano
• Figura tutte le combinazioni di elementi per ogni partizione (cioè l'insieme di potenza)
• take il prodotto di tutte queste combinazioni

Come così:

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