Encuentre todos los caminos a través de un árbol (dados nesteds) de arriba a abajo

EDITAR: vea a continuación una respuesta sugerida y cómo no está del todo bien todavía.

Hay muchas preguntas similares a esta en Stack Overflow, pero ninguna exactamente igual en Python. Soy un principiante en progtwigción, así que por favor, sea fácil.

Tengo un árbol de diccionarios nesteds, como este:

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

Quiero aplanar todos los caminos de arriba a abajo y terminar con esto:

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

Hice una pequeña y encantadora función recursiva que creó la estructura original en primer lugar, pero me cuesta mucho no recursivarla. Esto es hasta donde llegué:

 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 

… lo que devuelve esto:

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

… lo cual es claramente algo cercano, pero no del todo correcto.

Sé que esa función probablemente sea horriblemente no-Pythonic, pero me estoy enseñando a mí misma a progtwigr, por lo que ni siquiera estoy tratando de aprovechar las características del lenguaje que posiblemente existan y que me permitirían pensar en estas cosas desde cero ( “él dijo, publicando en un sitio de preguntas y respuestas con la esperanza de que sus miembros lo ayudaran a pensar un poco .

Entonces, ¿qué estoy haciendo mal?

EDIT : Moshe a continuación corrigió un par de problemas:

 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 

Esto está aún más cerca, pero no del todo bien:

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

Hay dos errores menores en eso:

1) all_combos current_combo lugar de all_combos . Eso solo te da tu último resultado.

2) En cada iteración , modifica current_combo . ¡Haga una copia primero!

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

Código 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 

Si pasa una copia de current_combo en la llamada recursiva, entonces no perderá su ruta actual en la siguiente iteración de su bucle for.

Además, no es necesario devolver current_combo, ya que el resultado no se usa en la recursión. Es posible que desee devolver all_combos en su lugar y no tomarlo como parámetro. Alternativamente, podría tener una función recursiva y ninguna función recursiva, con la función no recursiva creando la lista para all_combos y pasándola a la función recursiva de manera que la función recursiva podría asumir que all_combos estaba configurado.

Tomaría esta estrategia: para cada árbol,

  1. Recurse para calcular la lista de oraciones que vienen después de la palabra en la raíz de este árbol.
  2. Para cada oración, antepone la palabra actual delante de ella.
  3. Devuelve la lista de oraciones recién extendida.

¿Has hecho pruebas por inducción? Considero que la inducción es una de las técnicas matemáticas más útiles en mi progtwigción:

  1. Demuestre que su función maneja correctamente un árbol donde ‘next’ es None .
  2. Demuestre que su función maneja un árbol de profundidad n , asumiendo que puede manejar correctamente un árbol de profundidad n-1 .

La inducción luego extiende la prueba para cubrir árboles de cualquier profundidad. ¡Hecho!

Solo haciendo la respuesta de @ JoshHeitzman concreta (y simplificando sus parámetros predeterminados):

 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