Trova tutti i percorsi attraverso un albero (detti nidificati) dall'alto verso il basso

Question

MODIFICA: Vedi sotto per una risposta suggerita e come non è ancora abbastanza giusto.

Ci sono molte domande simili a questo su Stack Overflow, ma nessuno esattamente come in Python. Sono un novizio della programmazione, quindi per favore andate piano.

ho un albero di dizionari nidificate, in questo modo:

[{'word': 'The', 
    'next': [{'word': 'End', 
      'next': None}, 
      {'word': 'quick', 
      'next': [{'word': 'brown', 
         'next': [{'word': 'fox', 
           'next': None}]}]}, 
      {'word': 'best', 
      'next': [{'word': 'of', 
         'next': [{'word': 'times', 
           'next': None}]}]}]}] 

voglio appiattire tutti i percorsi da cima a fondo e finire con questo:

[[{'word': 'The'}, 
    {'word': 'End'}], 

[{'word': 'The'}, 
    {'word': 'quick'}, 
    {'word': 'brown'}, 
    {'word': 'fox'}], 

[{'word': 'The'}, 
    {'word': 'best'}, 
    {'word': 'of'}, 
    {'word': 'times'}]] 

ho fatto una bella una piccola funzione ricorsiva che ha creato la struttura originale in primo luogo, ma ho difficoltà a non ricrearla. Questo è quanto ho ottenuto:

def flatten_combinations(result_tree, current_combo = None, all_combos = None): 
    if current_combo is None: 
     current_combo = [] 
    if all_combos is None: 
     all_combos = [] 
    if result_tree is None: 
     all_combos.append(current_combo) 
     return 
    for word in result_tree: 
     current_combo.append({'word': word['word']}) 
     flatten_combinations(word['next'], current_combo, all_combos) 
    return current_combo 

... che restituisce questo:

[{'word': 'The'}, 
{'word': 'End'}, 
{'word': 'quick'}, 
{'word': 'brown'}, 
{'word': 'fox'}, 
{'word': 'best'}, 
{'word': 'of'}, 
{'word': 'times'}] 

... che è chiaramente un po 'stretta, ma non del tutto giusto.

So che questa funzione è probabilmente orribilmente non-Pythonic, ma mi sto insegnando a programmare, quindi non sto nemmeno cercando di sfruttare le funzionalità del linguaggio possibilmente esistenti che mi consentiranno di eludere il pensiero attraverso questa roba da scratch (", ha detto, postando a un Q & un sito nella speranza che i suoi membri lo aiutassero a elidere un po 'di pensiero).

Quindi: cosa sto sbagliando?

EDIT: Moshe sotto corretto un paio di problemi:

def flatten_combinations(result_tree, current_combo = None, all_combos = None): 
    if current_combo is None: 
     current_combo = [] 
    if all_combos is None: 
     all_combos = [] 
    if result_tree is None: 
     all_combos.append(current_combo) 
     return 
    for word in result_tree: 
     current_combo = current_combo[:] 
     current_combo.append({'word': word['word']}) 
     flatten_combinations(word['next'], current_combo, all_combos) 
    return all_combos 

Questo è più vicino ancora, ma non del tutto a destra:

[{'word': 'The'}, 
{'word': 'End'}], 

[{'word': 'The'}, 
{'word': 'End'}, 
{'word': 'quick'}, 
{'word': 'brown'}, 
{'word': 'fox'}], 

[{'word': 'The'}, 
{'word': 'End'}, 
{'word': 'quick'}, 
{'word': 'best'}, 
{'word': 'of'}, 
{'word': 'times'}]] 

Answer 1

ci sono due piccoli errori in che:

1) Si ritorna current_combo invece di . Questo ti dà solo il tuo ultimo risultato

2) Su ogni iterazione, si modifica current_combo. Fai prima una copia!

new_current_combo = current_combo[:] 
new_current_combo.append({'word': word['word']}) 
flatten_combinations(word['next'], new_current_combo, all_combos) 

codice completo:

def flatten_combinations(result_tree, current_combo=None, all_combos=None): 
    if current_combo is None: 
     current_combo = [] 
    if all_combos is None: 
     all_combos = [] 
    if result_tree is None: 
     all_combos.append(current_combo) 
     return 
    for word in result_tree: 
     new_current_combo = current_combo[:] 
     new_current_combo.append({'word': word['word']}) 
     flatten_combinations(word['next'], new_current_combo, all_combos) 
    return all_combos 

Answer 2

Se si passa in una copia del current_combo sul chiamata ricorsiva quindi non perderai il tuo percorso corrente alla successiva iterazione del ciclo for.

Inoltre, non è necessario restituire current_combo poiché il risultato non è utilizzato in ricorsione. Potresti voler restituire all_combos e non prenderlo come parametro. In alternativa, potresti avere una funzione ricorsiva e nessuna funzione ricorsiva, con la funzione non ricorsiva che crea l'elenco per tutti i combo e lo passa alla funzione ricorsiva in modo che la funzione ricorsiva possa assumere che all_combos sia stato impostato.

Answer 3

mi piacerebbe prendere questa strategia: per ogni albero,

1. Recurse per calcolare l'elenco delle frasi che vengono dopo la parola alla radice di questo albero.
2. Per ogni frase, anteporre la parola corrente.
3. Restituisce l'elenco di frasi appena esteso.

Avete fatto prove per induzione?Trovo l'induzione di essere una delle tecniche matematiche più utili nella mia programmazione:

1. Dimostrare che la funzione gestisce correttamente un albero dove 'prossimo' è None.
2. Provare che la funzione gestisce un albero di profondità n, presupponendo che possa gestire correttamente un albero di profondità n-1.

L'induzione estende quindi la prova per coprire alberi di qualsiasi profondità. Fatto!

Answer 4

solo facendo @ risposta concreta di JoshHeitzman (e semplificando i tuoi params di default):

def flatten_combinations(result_tree, current_combo = [], all_combos = []): 
if result_tree is None: 
    all_combos.append(current_combo) 
    return 
for word in result_tree: 
    current_combo.append({'word': word['word']}) 
    flatten_combinations(word['next'], current_combo[:], all_combos) 
return all_combos