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であることがわかっていますが、私は自分でプログラミングを教えているので、このようなものを最初から考え抜くことができる、存在する可能性のある言語機能を利用しようとさえしていません（」彼そのメンバーが彼が少し考えを取り除くのを助けることを期待してQ＆Aサイトに投稿すると言った）。

だから：私は何が間違っているのですか？

編集：以下のモシェはいくつかの問題を修正しました：

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 つです。

  1. 'next' が であるツリーを関数が正しく処理することを証明しますNone。
  2. n深さの木を正しく処理できると仮定して、関数が深さの木を処理できることを証明しますn-1。

帰納法は証明を拡張して、任意の深さの木をカバーします。終わり！

于 2012-11-13T01:03:35.017 に答える
1

これには、次の 2 つの小さな誤りがあります。

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 に答える