3

私は再帰に頭を悩ませようとしており、特定のリストのすべてのサブセットを生成するための実用的なアルゴリズムを投稿しました。

def genSubsets(L):
    res = []
    if len(L) == 0:
        return [[]]
    smaller = genSubsets(L[:-1])
    extra = L[-1:]
    new = []
    for i in smaller:
        new.append(i+extra)
    return smaller + new

私のリストがL = [0,1]で、正しい出力が[[]、[0]、[1]、[0,1]]であるとしましょう

print ステートメントを使用して、for ループに到達する前に genSubsets が 2 回呼び出されることを絞り込みました。それだけです。

しかし、なぜ最初の for ループは L の値を単に [0] として開始し、2 番目の for ループは [0,1] を使用するのでしょうか? for ループを組み込んだ再帰呼び出しはどのように機能しますか?

4

2 に答える 2

7

これは、ソースリストを長くすると実際に視覚化するのが簡単になると思います。を使用する[0, 1, 2]と、再帰呼び出しによってリストの最後の項目が繰り返し切り捨てられることがわかります。つまり、recusionは、次のような再帰呼び出しのスタックを構築します。

genSubsets([0,1,2])
    genSubsets([0,1])
        genSubsets([0])
            genSubsets([])

この時点で、再帰的アルゴリズムの「基本ケース」に到達します。この関数の基本的なケースは、パラメーターとして指定されたリストが空の場合です。基本ケースをヒットすると、空のリストを含むリストが返されます[[]]。スタックが戻ったときの外観は次のとおりです。

genSubsets([0,1,2])
    genSubsets([0,1])
        genSubsets([0]) <- gets [[]] returned to it

そのため、戻り値は前のレベルに戻り、smaller変数に保存されます。変数extraは、リストの最後の項目（この場合はコンテンツ全体）のみを含むスライスに割り当てられます[0]。

ここで、ループはの値を繰り返し処理し、それらの連結をにsmaller追加します。（空のリスト）には値が1つしかないため、値も1つだけになります。これはです。これは、ある時点で印刷している値だと思います。extranewsmallernew[]+[0][0]

次に、最後のステートメントはとの連結を返すsmallerためnew、戻り値は[[],[0]]です。スタックの別のビュー：

genSubsets([0,1,2])
    genSubsets([0,1]) <- gets [[],[0]] returned to it

戻り値はsmaller再び割り当てられ、extraは[1]であり、ループが再び発生します。今回は、new2つの値を取得[1]します[0,1]。それらは再び最後に連結されsmaller、戻り値は[[],[0],[1],[0,1]]です。最後のスタックビュー：

genSubsets([0,1,2]) <- gets [[],[0],[1],[0,1]] returned to it

同じことが再び起こりますが、今回2はこれまでに見つかった各アイテムの最後にsを追加します。newとして終わります[[2],[0,2],[1,2],[0,1,2]]。

最終的な戻り値は[[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]

于 2012-12-06T06:45:42.847 に答える
3

私は、再帰関数が何をするのかを理解するために、コール グラフ全体を視覚化しようとするのが好きではありません。

もっと簡単な方法があると思います：

再帰関数が正しいことを行うおとぎ話の世界に入りましょう™。

それがうまくいくと仮定しgenSubsets(L)てください：

# This computes the powerset of the list L minus the last element
smaller = genSubsets(L[:-1])

これは魔法のように機能したため、欠落しているエントリは最後の要素を含むものだけです。

このフラグメントは、不足しているすべてのサブセットを構築します。

new = []
for i in smaller:
    new.append(i+extra)

の最後の要素を含むサブセットと、最後の要素を含まないnewサブセットがあります。smaller

したがって、すべてのサブセットが必要になるため、 を返すことができnew + smallerます。

残っているのは、再帰が停止することを確認するための基本ケースだけです。空集合 (この場合はリスト) はすべての累乗集合の要素であるため、それを使用して再帰を停止できます。空集合の累乗集合を要求することは、空集合を含む集合です。したがって、基本ケースは正しいです。すべての再帰ステップはリストから 1 つの要素を削除するため、基本ケースはいつか遭遇する必要があります。

したがって、コードは実際にベキ集合を生成します。

注: この背後にある原理は、誘導の原理です。ある既知のn 0に対して何かが機能する場合n、次のn+1ことを証明できます。

于 2012-12-06T09:38:29.157 に答える