1

Phillip Fuchs 教授は、純粋な反復法 (quickperm.org を参照) を使用してオブジェクトの配列の順列を生成するための非常に優れたアルゴリズムを持っています。基本的には、カウントダウン アルゴリズムとカウンティング (カウントアップ) アルゴリズムの 2 つのバリエーションがあります。アイデアは同じで、初期化の問題と、「オドメーター」の数字を増減するかどうかが異なるだけです。

私はしばらくアルゴリズムを調べましたが、1 つの特定の詳細を除いて、アイデアを理解できます。アルゴリズムと、フックス教授が彼のアルゴリズムに提供した説明では、高指数が偶数の場合、低指数は 0 に設定されると述べています。高位インデックスが奇数の場合、低位インデックスは高位インデックスが指す「走行距離」桁に設定されます (元のテキストでは j、i、および p[] が使用されます)。

lowIndex = (highIndex %2 == 0) ? 0 : odometerDigit[highIndex];

このロジックを理解するのに苦労しています。highIndex が偶数または奇数であると、lowIndex が 0 または odometerDigit の値であると判断されるのはなぜですか? フックス教授はこれについてより詳細な説明を提供していませんが、これはアルゴリズムの「魔法の」核心です。これをさらに理解するのに役立つ洞察をいただければ幸いです。

4

1 に答える 1

2

N = 5 (!) を踏んだので、これを突き刺します。

再帰に対する Fuchs の [要出典] の態度はさておき、何が起こっているのかを説明する 1 つの方法は、彼が次の再帰アルゴリズムをいじっているということだと思います。これがあなたにとって魔法ではないことを願っています。

def permute0(lst, n):
    if n < 2:
        print(lst)
    else:
        for j in range(n - 1, -1, -1):  # j in [0, n) descending
            # generate permutations with lst[n - 1] fixed
            lst[j], lst[n - 1] = lst[n - 1], lst[j]  # swap
            permute0(lst, n - 1)
            lst[j], lst[n - 1] = lst[n - 1], lst[j]  # swap back

最初の最適化は、内部スタック フレームでは、変数の値のみjを、呼び出した配列に格納する必要があることpです。私はそれを気にするつもりはありません。

2番目の最適化は、彼がスワップ切除を行ったことです. 要素をそれ自体と交換しないことで、交換を少し減らすことができます。

def permute1(lst, n):
    if n < 2:
        print(lst)
    else:
        permute1(lst, n - 1)
        for j in range(n - 2, -1, -1):
            lst[j], lst[n - 1] = lst[n - 1], lst[j]
            permute1(lst, n - 1)
            lst[j], lst[n - 1] = lst[n - 1], lst[j]

スワップの回数をさらに減らすには、より賢くする必要があります。permute2、以前のバージョンとは異なり、lst戻る前に復元しません。汚い仕事をするpermute2ために使用するため、再帰的ではありません。permute1

def permute2(lst, n):
    if n < 2:
        print(lst)
    else:
        permute1(lst, n - 1)
        for j in range(n - 2, -1, -1):
            lst[j], lst[n - 1] = lst[n - 1], lst[j]
            permute1(lst, n - 1)

に何をしpermute2ますlstか？変更されないへの呼び出しを無視して、permute11つの要素を左lstに回転します。lstこれで、スワップする次の要素をpermute2a呼び出して探しますが、s のタワー全体を記述することはできません。permute2lst[n - 1]permute2permute

permute次の関数を証明するために使用できる、まだ存在していない関数の動作に関する帰納的な仮説が必要です。これは創造的な行為であり、コンピューター サイエンスにおける多くの「魔法」の源です。これから書くことは、おそらく私の考えを現実的に描いたものではありません。

私たちが調べているアルゴリズムのクラスには、2 つの自然な制約があります。まず、これらのアルゴリズムは最小数のスワップを行います。第二に、それらは自己相似であり、最後の要素を移動する前に、最初の N - 1 要素のすべての順列を使い果たします。一緒に、これらの制約により、スワップされた要素の 1 つが Fuchs の に対応する場所に格納されますi。

N = 0: there's only one permutation
N = 1: there's only one permutation
N = 2: the graph looks like 0 1 - 1 0
N = 3: the graph looks like

0 1 2   1 2 0   2 0 1
  |       |       |
   -------+-------     all bipartite connections
  |       |       |
0 2 1   2 1 0   1 0 2

で一般性を失うことなく開始し0 1 2ます。( の初期内容はlst問いません。) それでは、開始する必要があります。

0 1 2  # forced w.l.o.g.
1 0 2  # forced because 2 cannot be moved yet.

ここで唯一興味深い選択が生じます。私たちは終えることができました

2 0 1  # chose 1
0 2 1  # forced because 1 cannot be moved yet
1 2 0  # forced because we must move element 1 and 0 1 2 is already visited
2 1 0  # forced because 0 cannot be moved yet.

他に考えられる継続は

1 2 0  # chose 0
2 1 0  # forced because 0 cannot be moved yet
2 0 1  # forced because we must move element 0 and 0 1 2 is already visited
0 2 1  # forced because 1 cannot be moved yet.

この時点で、N = 2 と N = 3 の最初の可能性は両方とも順列が逆になっていることに気付きました。permute3その逆を構築してみlstます。N = 4 の場合にどうなるか見てみましょう。

0 1 2 3
...
2 1 0 3
3 1 0 2
...
0 1 3 2
0 2 3 1
...
3 2 0 1
3 2 1 0
...
1 2 3 0  # oops

まあ、それはうまくいきませんでした。サブ配列を反転させておくには、奇数回の再帰呼び出しが必要です。iこれは、奇数と偶数で異なる動作が必要かもしれないという最初の提案ですi。

のようpermute2に、N = 4 の場合、この仮想アルゴリズムは要素を 1 つ左に回転させます。そのテーマのバリエーションは行き止まりのようです。ここでは十分に遅く、実りのない実験を十分に行ったので、フックスのアルゴリズムも魔法のように見え始めています。

やっぱり書かせてくださいpermute2a。1 つの要素を左にpermute2回転することを思い出してください。回転を補正しながら位置を増やしてスワップを行うlst場合、同じ位置を繰り返しスワップします (他の位置にアクセスできることが保証されていないため)。permute2aj0

def permute2a(lst, n):
    if n < 2:
        print(lst)
    else:
        permute2(lst, n - 1)
        for j in range(n - 2, -1, -1):
            lst[0], lst[n - 1] = lst[n - 1], lst[0]
            permute2(lst, n - 1)

ここで、 の代わりに がpermute2呼び出された場合、ペアはフックスのアルゴリズムとほぼ同等になることに気付いた瞬間です。これは私にはまだ魔法のように思えますが、それを終わらせる時が来ました. 多分明日。permute2apermute1

実際、permute2aは左回転だけでなく、そこからの任意の固定順列もpermute2サイクルで処理できます。つまり、順列がそのドメイン内の単一の要素に繰り返し適用されると、他のすべての要素が得られます。がpermute2このように動作すると、 の効果はの (N - 1) サイクル順列を N 回permute2a適用することpermute2ですが、サイクル間で要素を位置 0 に出し入れすることを除いて、各要素がサイクルに沿って移動する効果があります。 N - 1 回、効果はありません。permute2aonの効果はlst、 に関係なく、permute2位置 0 と N - 1 を交換することです。

permute2あとは、が を使用できると主張するだけpermute2aです。permute2aの動作がの実装の詳細に左右されないという事実に、私たちは大いに助けられていますpermute2。さらに、permute2aは部分配列の最初と最後の要素にしか触れないため、 の現在の実装permute2はほぼそのままです。実際、N が偶数の場合、そのまま機能します。

0123
...
2103
2130
...
3120
3021
...
2031
1032
...
3012

N 奇数の問題は、同じ要素が最後の位置に 2 回スワップされることです。

01234
...
31204
31240
...
41230
41032
...
31042
32041
...
42031
12034  # oops

あとは、newpermute2がその要素を循環することを示すだけです (N が偶数の場合)。単純な初等証明が見えないので、群論を少し使ってみます。循環表記では、順列は

(0 n-2)(0 n-1)(0 n-2)(1 n-1)(0 n-2)...(0 n-2)(n-3 n-1)(0 n-2)(n-2 n-1)(0 n-2).

バラバラな自転車通勤。

(0 n-2)(0 n-1)[(0 n-2)...n-2 times...(0 n-2)](1 n-1)...(n-3 n-1)(n-2 n-1)(0 n-2).

n は偶数なので、n-2 回連続してスワップしても効果はありません。

(0 n-2)(0 n-1)(1 n-1)...(n-3 n-1)(n-2 n-1)(0 n-2).

シーケンス(0 n-1)(1 n-1)...(n-3 n-1)(n-2 n-1)は、前に見たように、サイクルです。

(0 n-2)(0 n-1 n-2 ... 1)(0 n-2).

これは共役サイクルであり、サイクルでもあります。

(0 n-3 n-4 ... 1 n-2 n-1).

これが最終版です。私は、明示的なスタックを法とする Fuchs のアルゴリズムと同等であると主張します。

def permute3(lst, n):
    if n < 2:
        print(lst)
    else:
        permute3(lst, n - 1)
        for k in range(n - 2, -1, -1):
            i = n - 1
            j = 0 if i % 2 == 0 else k
            lst[j], lst[i] = lst[i], lst[j]
            permute3(lst, n - 1)
于 2013-04-16T03:59:39.373 に答える