从顶部到底部查找通过树（嵌套式）的所有路径 [英] Find all paths through a tree (nested dicts) from top to bottom
问题描述
编辑：请参阅下面的建议答案，以及如何不正确。
有很多类似的问题这一个在Stack Overflow上，但在Python中完全没有。我是一个编程新手，所以请轻松一点。
我有一堆嵌套的字典，如下所示：
[{'word'：'The'，
'next'：[{'word'：'End'，
'next '：无}，
{'word'：'quick'，
'next'：[{'word'：'brown'，
'next'：[{'word' 'fox'，
'next'：无}]}]，
{'word'：'best'，
'next'：[{'word'：'of'
'next'：[{'word'：'times'，
'next'：None}]}]}]}]
我想从上到下平铺所有路径，最终结束：
[[{'word'：'''，
{'word'：'End'}]，
[{'word'：'The'}，
{'word'：'quick'}，
{'word'：'brown'}，
{ 'word'：'fox'}]，
[{'word'：'The'}，
{'word'：'best'}，
{'word '：'of'}，
{'word'：'times'}]]
我做了一个可爱的小递归函数，它首先创建了原始的结构，但是我很难重新考虑它。这是我所得到的：
def flatten_combination（result_tree，current_combo = None，all_combos = None）：
如果current_combo为None：
current_combo = []
如果all_combos为None：
all_combos = []
如果result_tree为无：
all_combos.append（current_combo）
返回
在result_tree中的单词：
current_combo.append（{'word'：word ['word']}）
flatten_combinations（word ['next']，current_combo，all_combos ）
return current_combo
...这返回：
[{'word'：'The'}，
{'word'：'End'}，
{'word'：'
{'word'：'brown'}，
{'word'：'fox'}，
{'word'：'best'}，
{'word'：'of'}，
{'word'：'times'}]
...这显然有点接近，但不太正确。
我知道这个功能可能是非常不协调的，但是我正在教自己编程，所以我甚至不想利用可能存在的语言功能，让我无法想象这个东西从头开始（他说，发贴到一个Q&A的一个网站，希望其成员能帮助他一点想法）。
编辑：Moshe以下更正了一些问题：
def flatten_combinations（result_tree，current_combo = None，all_combos = None）：
如果current_combo为None：
current_combo = []
如果all_combos为None：
all_combos = []
如果result_tree为无：
all_combos.append（current_combo）
返回
在result_tree中的单词：
current_combo = current_combo [：]
current_combo.append（{'word'：word ['word']}）
flatten_组合（word ['next']，current_combo，all_combos）
return all_combos
但还不太正确：
[{'word'：'The'}，
{' '：'End'}]，
[{'word'：'The'}，
{'word'：'End'}，
{'word' 'b'b'''''''''，'b' '}，
{'word'：'End'}，
{'word'：'quick'}，
{'word'：'best'}，
{ ''''''，
{'word'：'times'}]]
有两个小错误：
1）您返回 current_combo 而不是 all_combos 。这只会给你最后的结果
2）在每个迭代上，你修改 current_combo 。
new_current_combo = current_combo [：]
new_current_combo.append（{'word'：word [ 'word']}）
flatten_combinations（word ['next']，new_current_combo，all_combos）
全部代码：
def flatten_combinations（result_tree，current_combo = None，all_combos = None）：
如果current_combo没有：
current_combo = []
如果all_combos为None：
all_combos = []
如果result_tree为无：
all_combos.append（current_combo）
对于result_tree中的单词返回
：
new_current_combo = current_combo [：]
new_current_combo.append（{'word'：word ['word']}）
flatten_combinations（word [下一个']，new_current_combo，all_combos）
返回all_combos
EDIT: See below for a suggested answer and how it's not quite right yet.
There are many similar questions to this one on Stack Overflow, but none exactly like it in Python. I'm a programming novice, so please go easy.
I have a tree of nested dictionaries, like this:
[{'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}]}]}]}]
I want to flatten all paths from top to bottom and end up with this:
[[{'word': 'The'},
{'word': 'End'}],
[{'word': 'The'},
{'word': 'quick'},
{'word': 'brown'},
{'word': 'fox'}],
[{'word': 'The'},
{'word': 'best'},
{'word': 'of'},
{'word': 'times'}]]
I made a lovely little recursive function that created the original structure in the first place, but I'm having a hard time unrecursivizing it. This is as far as I got:
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
…which returns this:
[{'word': 'The'},
{'word': 'End'},
{'word': 'quick'},
{'word': 'brown'},
{'word': 'fox'},
{'word': 'best'},
{'word': 'of'},
{'word': 'times'}]
…which is clearly somewhat close, but not quite right.
I know that function is probably horribly un-Pythonic, but I'm teaching myself programming, so I'm not even trying to take advantage of possibly-existent language features that would let me elide over thinking through this stuff from scratch (" he said, posting to a Q&A site in the hope its members would help him elide a bit of thought).
So: what am I doing wrong?
EDIT: Moshe below corrected a couple of problems:
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
This is closer yet, but not quite right:
[{'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'}]]
There are two minor mistakes in that:
1) You return current_combo instead of all_combos. That only gives you your last result
2) On each iteration, you modify current_combo. Make a copy first!
new_current_combo = current_combo[:]
new_current_combo.append({'word': word['word']})
flatten_combinations(word['next'], new_current_combo, all_combos)
Full code:
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
这篇关于从顶部到底部查找通过树（嵌套式）的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
