6

编辑：请参阅下面的建议答案以及它是如何还不完全正确的。

Stack Overflow 上有很多与此类似的问题，但没有一个与 Python 中的完全一样。我是一个编程新手，所以请放轻松。

我有一棵嵌套字典树，如下所示：

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

我想从上到下展平所有路径并最终得到这个：

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

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

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

我做了一个可爱的小递归函数，它首先创建了原始结构，但我很难取消递归它。据我所知：

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

…返回这个：

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

…这显然有点接近，但并不完全正确。

我知道这个函数可能非常不符合 Python 风格，但我正在自学编程，所以我什至没有尝试利用可能存在的语言特性，这些特性会让我从头开始思考这些东西（”他说，张贴到一个问答网站，希望它的成员能帮助他消除一点想法）。

所以：我做错了什么？

编辑：下面的 Moshe 纠正了几个问题：

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

这更接近了，但并不完全正确：

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

4 回答 4

1

如果您在递归调用中传入 current_combo 的副本，那么您不会在 for 循环的下一次迭代中丢失当前路径。

此外，您不需要返回 current_combo，因为结果不用于递归。您可能希望返回 all_combos 而不是将其作为参数。或者，您可以有一个递归函数和一个非递归函数，其中非递归函数为 all_combos 创建列表并将其传递给递归函数，以便递归函数可以假定 all_combos 已设置。

于 2012-11-13T01:02:26.563 回答
1

我会采取这个策略：对于每棵树，

  1. 递归计算在这棵树的根词之后的句子列表。
  2. 对于每个句子，在其前面添加当前单词。
  3. 返回新扩展的句子列表。

你做过归纳证明吗？我发现归纳是我编程中最有用的数学技术之一：

  1. 证明您的函数正确处理了 'next' 所在的树None。
  2. 证明您的函数处理深度树n，假设它可以正确处理深度树n-1。

归纳然后将证明扩展到覆盖任何深度的树。完毕！

于 2012-11-13T01:03:35.017 回答
1

其中有两个小错误：

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):
    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
于 2012-11-13T01:08:31.680 回答
0

只是使@JoshHeitzman 的答案具体化（并简化您的默认参数）：

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
于 2012-11-13T01:10:22.253 回答