31

itertools.permutations誰かが Python 標準 lib 2.6 のルーチンのアルゴリズムを説明できますか? なぜそれが機能するのかわかりません。

コードは次のとおりです。

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return
4

2 に答える 2

36

「軌道」とも呼ばれる順列サイクルの数学的理論を理解する必要があります(組み合わせ論の中心である数学的主題は非常に高度であり、研究を調べる必要がある場合があるため、両方の「技術用語」を知っておくことが重要です)。いずれかまたは両方の用語を使用できる論文）。

順列の理論の簡単な紹介については、ウィキペディアが役立ちます。私が言及した各 URL は、組み合わせ論に魅了されて、それをさらに探求し、真の理解を得たいと思うなら、合理的な文献目録を提供します (個人的にはそうしました -- 趣味のようなものになっています;-)。

数学的理論を理解したとしても、コードはまだ微妙で、「リバース エンジニアリング」にとって興味深いものです。明らかに、indicesはプールへのインデックスに関する現在の順列にすぎません。

yield tuple(pool[i] for i in indices[:r])

したがって、この魅力的な機構の核心は でありcycles、これは順列の軌道を表しindices、主にステートメントによって更新される原因となります

j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]

cycles[i]つまり、がの場合j、インデックスの次の更新では、(左から) i 番目のものを右からj 番目のものと交換することを意味します(たとえば、jが 1 の場合、 の最後の要素indicesは交換 -- indices[-1])。そして、cyclesデクリメント中に の項目が 0 に達したときの頻度の低い「一括更新」があります。

indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i

これは のi番目の項目をindices最後に配置し、インデックスの後続のすべての項目を 1 つ左にシフトし、次に のこの項目に来たときに(左から)cyclesの新しい4i番目の項目を1 つ目 (右から) -- それはindicesまた1 つ目です。n - ii

cycles[i] -= 1

次に調べる前に;-)。

もちろん難しいのは、これが機能することを証明することです。つまり、すべての順列が重複せずに、正確に「タイミングを合わせて」終了するように徹底的に生成されることです。証明の代わりに、ステートメントをコメントアウトしてyieldステートメントを追加printする (Python 2.*) など、単純なケースで完全に公開されたときに機械がどのように機能するかを確認する方が簡単かもしれないと思います。

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    print 'I', 0, cycles, indices
    # yield tuple(pool[i] for i in indices[:r])
    print indices[:r]
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
        print 'B', i, cycles, indices
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
        print 'A', i, cycles, indices
            else:
        print 'b', i, cycles, indices
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
        print 'a', i, cycles, indices
                # yield tuple(pool[i] for i in indices[:r])
            print indices[:r]
                break
        else:
            return

permutations('ABC', 2)

これを実行すると、次のようになります。

I 0 [3, 2] [0, 1, 2]
[0, 1]
b 1 [3, 1] [0, 1, 2]
a 1 [3, 1] [0, 2, 1]
[0, 2]
B 1 [3, 0] [0, 2, 1]
A 1 [3, 2] [0, 1, 2]
b 0 [2, 2] [0, 1, 2]
a 0 [2, 2] [1, 0, 2]
[1, 0]
b 1 [2, 1] [1, 0, 2]
a 1 [2, 1] [1, 2, 0]
[1, 2]
B 1 [2, 0] [1, 2, 0]
A 1 [2, 2] [1, 0, 2]
b 0 [1, 2] [1, 0, 2]
a 0 [1, 2] [2, 0, 1]
[2, 0]
b 1 [1, 1] [2, 0, 1]
a 1 [1, 1] [2, 1, 0]
[2, 1]
B 1 [1, 0] [2, 1, 0]
A 1 [1, 2] [2, 0, 1]
B 0 [0, 2] [2, 0, 1]
A 0 [3, 2] [0, 1, 2]

に焦点を当てますcycles: それらは 3, 2 として始まります -- 最後のイベントはデクリメントされるため、3, 1 -- 最後はまだゼロではないため、「小さな」イベント (インデックスの 1 つのスワップ) が発生し、内側のループ。次に、もう一度入力します。今回は、最後のデクリメントが 3, 0 になります。最後の値が 0 になったので、これは「大きな」イベントです。つまり、インデックスの「質量スワップ」です (まあ、ここには質量はあまりありませんが、しかし、あるかもしれません;-) そしてサイクルは 3, 2 に戻ります。-to-last (この場合は最初の) -- これは、マイナー イベント、インデックスの 1 つのスワップを提供し、内側のループを再び中断します。ループに戻ると、再び最後のループがデクリメントされ、今度は 2、1 になります -- マイナー イベントなどです。最終的に for ループ全体が発生し、メジャー イベントのみが発生し、マイナー イベントは発生しません。サイクルはすべて 1 として開始されます。 、したがって、デクリメントはそれぞれをゼロ (主要なイベント) にyieldし、その最後のサイクルでは発生しません。

breakそのサイクルで実行されたことがないので、返される のelse分岐を取りforます。は少し誤解を招く可能性があることに注意してくださいwhile n。実際にはwhile True--n変化せず、whileループはそのreturnステートメントからのみ終了します。もちろん、is (空の「プール」) の場合、最初の些細な empty のif not n: return後に生成するものは何もないためです。作成者は、チェックを;-)で折りたたんで数行を節約することにしました。while True:n0yieldif not n:while

さらにいくつかの具体的なケースを検討することをお勧めします。最終的には、「時計仕掛け」が動作していることに気付くはずです。最初だけに焦点を当てます (ステートメントを適切にcycles編集して削除することもできます)。これは、軌道を時計仕掛けのように進むことが、この微妙で深いアルゴリズムの鍵であるためです。あなたがそれを理解したら、のシーケンスに応じて適切に更新される方法は、ほとんどアンチクライマックスです!-)printindicesindicescycles

于 2010-04-02T15:24:45.853 に答える