1

この順列アルゴリズムを説明してくれる人はいますか? 私はそれが置換を行うことを知っていますが、なぜそれが機能するのかわかりません。 

s = [1,2,3,4,5,6,7,8,9]  
def perm(s, i):
    if i == len(s):
        print s
    for j in range(i, len(s)):
        s[i], s[j] = s[j], s[i]
        perm(s, i + 1)
        s[i], s[j] = s[j], s[i]  //why it swaps back?
4

2 に答える 2

2

この関数は、配列sを可能な順列ごとに変更してから、順列を出力し、元に戻すときに変更を元に戻します。

各 positionで、インデックスが単独iよりも小さいすべてのエントリを残し、それ以降のすべての値を position で試行し、再帰を使用して、固定値のセットと position にあるものに対する各選択肢を使用してすべての順列を見つけます。最高のインデックスでは、残りの選択肢はありませんが、順列の 1 つが見つかったため、結果としてそれが出力されます。iii

この種の再帰を理解するには、関数の開始と終了、この場合はスワップなどの興味深いポイントでコードに追加の「デバッグ プリント」を入れると役立ちます。

これは確かに最も洗練された Python ではありません (デバッグ プリントの一部を関数に抽出する必要があります)。

def perm(s, i):
    print '{padding}starting perm({list}, {index})'.format(list=s, index=i, padding=' '*i)
    if i == len(s):
        print s
    for j in range(i, len(s)):
        print '{padding}swapping s[{index1}]={entry1} and s[{index2}]={entry2}'.format(index1=i, entry1=s[i], index2=j, entry2=s[j], padding=' '*i)
        s[i], s[j] = s[j], s[i]
        perm(s, i + 1)
        print '{padding}swapping back s[{index1}]={entry1} and s[{index2}]={entry2}'.format(index1=i, entry1=s[i], index2=j, entry2=s[j], padding=' '*i)
        s[i], s[j] = s[j], s[i]
    print '{padding}returning from perm({list}, {index})'.format(list=s, index=i, padding=' '*i)
于 2012-06-09T13:47:40.397 に答える
0

これは、(リスト) が変更可能であることを意味する Python コードであるため、元に戻すためs、呼び出された関数で変更が加えられた場合、呼び出し元の配列に影響します。

スワップバックしなかった場合、呼び出しが戻った後、配列は「奇妙な」状態になります (以前の呼び出しによって残されます)。

突然変異を必要としない代替案は次のとおりです。

s = [1,2,3,4,5,6,7,8,9]  
def perm(s, i):
    s = list(s) # copy before mutating
    if i == len(s):
        print s
    for j in range(i, len(s)):
        s[i], s[j] = s[j], s[i]
        perm(s, i + 1)

または、おそらくより明確に:

    s = [1,2,3,4,5,6,7,8,9]
    デフォルトパーマ(s、i):
        i == len(s) の場合:
            プリント
        範囲内の j の場合 (i, len(s)):
            s[i]、s[j] = s[j]、s[i]
            perm(list(s), i + 1) # コピーを渡す

これが反対票を投じられた理由がわからないコメント。ユーザーは同時に質問にいくつかのコメントをしましたが、その後それらを削除しました。私は彼らが間違っていたと思います、そしてコメントを削除することは彼らがそれを認識したことを意味すると思いますが、なぜ彼らが反対票も削除しなかったのかわかりません(それが彼らのものである場合)。または、これが間違っている場合は、誰かが説明してください。私が学ぶことができます...

于 2012-06-05T14:28:01.417 に答える