Znajdź wszystkie ścieżki w drzewie (zagnieżdżone dyktety) od góry do dołu.

Question

EDYCJA: Zobacz poniżej, aby uzyskać sugerowaną odpowiedź i jak to jeszcze nie jest w porządku.

Jest wiele podobnych pytań do tego na Stack Overflow, ale żaden dokładnie taki jak w Pythonie. Jestem początkującym programistą, więc proszę, idź łatwo.

Mam drzewo zagnieżdżonych słowników, tak:

[{'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}]}]}]}] 

Chcę spłaszczyć wszystkie ścieżki od góry do dołu i skończyć z tym:

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

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

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

Zrobiłem piękny mała funkcja rekursywna, która stworzyła oryginalną strukturę, ale trudno mi ją zneutralizować. To ile mam:

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 

... który powraca w ten sposób:

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

... co jest wyraźnie dość blisko, ale nie całkiem w porządku.

Wiem, że ta funkcja jest prawdopodobnie okropnie nie-Pythonic, ale uczę się programowania, więc nie próbuję nawet korzystać z ewentualnych funkcji językowych, które pozwoliłyby mi wymknąć się z tego, scratch (", powiedział, publikując na Q & Stronę w nadziei, że jej członkowie pomogą mu wymyślić trochę myśli).

A więc: co robię źle?

EDIT: Moshe poniżej poprawione kilka problemów:

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 

Jest bliżej jeszcze, ale nie w porządku:

[{'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

Istnieją dwa drobne błędy w tym:

1) powrót current_combo zamiast . To daje tylko twój ostatni wynik:

2) Przy każdej iteracji iteracji, modyfikujesz current_combo. Najpierw wykonaj kopię!

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

Pełny kod:

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

Jeśli przekazana w kopii current_combo w sprawie wywołanie rekurencyjne, wtedy nie stracisz swojej obecnej ścieżki podczas kolejnej iteracji pętli for.

Nie trzeba również zwracać wartości current_combo, ponieważ wynik nie jest używany w rekursji. Zamiast tego możesz chcieć zwrócić all_combos i nie brać go jako parametru. Alternatywnie możesz mieć funkcję rekursywną i żadną funkcję rekursywną, z funkcją bez rekurencji tworzącą listę dla all_combos i przekazującą ją do funkcji rekursywnej, dzięki czemu funkcja rekursywna mogłaby zakładać, że all_combos został ustawiony.

Answer 3

zabrałbym tę strategię: Dla każdego drzewa,

1. recurse obliczyć listę zdań, które przychodzą po słowie na korzeń tego drzewa.
2. Dla każdego zdania, poprzedzaj bieżące słowo przed nim.
3. Zwróć nowo rozszerzoną listę zdań.

Czy zrobiłeś dowody przez indukcję?Uważam, indukcyjnej za jeden z najbardziej przydatnych technik matematycznych w moim programowania:

1. Udowodnić, że funkcja poprawnie obsługuje drzewa gdzie „Next” jest None.
2. Wykaż, że twoja funkcja obsługuje drzewo o głębokości n, zakładając, że może poprawnie obsługiwać drzewo o głębokości n-1.

Indukcja rozszerza wówczas dowód na drzewa o dowolnej głębokości. Gotowe!

Answer 4

tylko co @ odpowiedzi betonu JoshHeitzman (oraz uproszczenie domyślne params):

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