サイクル リーダー反復アルゴリズムは、相対的な順序を維持しながら、すべての偶数番号のエントリを前に移動し、すべての奇数番号のエントリを後ろに移動することによって、配列をシャッフルするアルゴリズムです。たとえば、次の入力があるとします。
a 1 b 2 c 3 d 4 e 5
出力は次のようになります
a b c d e 1 2 3 4 5
このアルゴリズムは O(n) 時間で実行され、O(1) スペースのみを使用します。
このアルゴリズムの特殊な詳細の 1 つは、配列をサイズ 3 k +1のブロックに分割することによって機能することです。どうやらこれはアルゴリズムが正しく機能するために重要なのですが、その理由はわかりません。
アルゴリズムで 3 k + 1 の選択が必要なのはなぜですか?
ありがとう！
これは長い答えになるでしょう。あなたの質問への答えは単純ではなく、完全に答えるにはいくつかの数論が必要です。半日かけてアルゴリズムを調べた結果、良い答えが得られましたが、簡潔に説明できるかどうかはわかりません。
入力をサイズ 3 k + 1 のブロックに分割すると、基本的に入力がサイズ 3 k - 1 のブロックに分割され、最終的に移動しない 2 つの要素に囲まれます。
ブロック内の残りの 3 k - 1 要素は、興味深いパターンに従って移動します。各要素は、インデックスを 3 kを法とする 2 で割った位置に移動します。
この特定の運動パターンは、原始根と呼ばれる数論と群論の概念に関連しています。
数値 2 は 3 kを法とする原始根であるため、数値 1、3、9、27などで始まり、パターンを実行すると、配列のすべての要素を 1 回だけ循環し、適切な場所に配置することが保証されます。 .
このパターンは、任意の k ≥ 1 に対して 2 が 3 kの原始根であるという事実に大きく依存しています。配列のサイズを別の値に変更すると、間違ったプロパティが保持されるため、ほぼ確実にこれが壊れます。
この答えを提示するために、段階的に進めていきます。最初に、要素を正しい順序で効率的にシャッフルするアルゴリズムの動機として、循環分解を紹介しますが、重要な注意事項があります。次に、この順列を適用したときに要素が配列内でどのように移動するかという興味深い特性を指摘します。次に、これを原始根と呼ばれる数論的概念に結び付けて、このアルゴリズムを正しく実装する際の課題について説明します。最後に、ブロック サイズとして 3 k + 1が選択される理由を説明します。
配列 A と、その配列の要素の順列があるとします。標準的な数学表記に従って、その配列の順列を σ(A) と表します。最初の配列 A を並べ替えられた配列 σ(A) の上に並べて、すべての要素がどこで終了したかを把握できます。たとえば、配列とその順列の 1 つを次に示します。
A 0 1 2 3 4
σ(A) 2 3 0 4 1
順列を説明する 1 つの方法は、その順列内の新しい要素を列挙することです。ただし、アルゴリズムの観点からは、順列を循環分解として表す方が役立つことがよくあります。これは、最初の配列から始めて、その要素の一部を循環的に順列することによって順列を形成する方法を示すことで、順列を書き出す方法です。
上記の順列を見てください。まず、0 がどこにあるのかを確認します。σ(A) では、要素 0 が元の要素 2 に取って代わりました。次に、要素 2 は、要素 0 があった場所に取って代わりました。これを (0 2) と書き、2 があった場所に 0 を移動し、0 があった場所に 2 を移動することを示します。
ここで、要素 1 を見てください。要素 1 は、元の 4 の場所になりました。その後、数字の 4 は 3 があった場所に配置され、要素 3 は 1 が配置されていた場所に配置されました。これを (1 4 3) と書き、1 は 4 があった場所に移動し、4 は 3 があった場所に移動し、3 は 1 があった場所に移動することを示します。
これらを組み合わせると、上記の要素の全体的な順列を (0 2)(1 4 3) として表すことができます。つまり、0 と 2 を入れ替えてから、1、4、3 を循環的に並べ替える必要があります。配列、必要な並べ替えられた配列になります。
サイクル分解は、O(C) 時間と O(1) 補助空間 (C はサイクル内の要素の数) で個々のサイクルを並べ替えることができるため、配列をその場で並べ替えるのに非常に役立ちます。たとえば、サイクル (1 6 8 4 2) があるとします。次のようなコードを使用して、サイクル内の要素を並べ替えることができます。
int[] cycle = {1, 6, 8, 4, 2};
int temp = array[cycle[0]];
for (int i = 1; i < cycle.length; i++) {
swap(temp, array[cycle[i]]);
}
array[cycle[0]] = temp;
これは、すべてが落ち着くまですべてを交換するだけで機能します。サイクル自体を格納するために必要なスペースの使用量を除けば、必要なのは O(1) の補助ストレージ スペースだけです。
一般に、要素の配列に特定の順列を適用するアルゴリズムを設計する場合、通常は循環分解を使用して設計できます。一般的なアルゴリズムは次のとおりです。
for (each cycle in the cycle decomposition algorithm) {
apply the above algorithm to cycle those elements;
}
このアルゴリズムの全体的な時間と空間の複雑さは、次の要素に依存します。
当面の問題に対する O(n) 時間、O(1) 空間アルゴリズムを取得するために、O(1) 時間と空間でサイクル分解を決定する方法があることを示します。すべてが一度だけ移動されるため、全体の実行時間は O(n) になり、全体のスペースの複雑さは O(1) になります。ご覧のとおり、そこにたどり着くのは簡単ではありませんが、それでもひどいことではありません。
この問題の最も重要な目標は、2n 要素の配列を取り、それをシャッフルして、偶数位置の要素が配列の先頭に配置され、奇数位置の要素が配列の最後に配置されるようにすることです。ここでは、次のように 14 個の要素があるとします。
0 1 2 3 4 5 6 7 8 9 10 11 12 13
次のようになるように要素をシャッフルします。
0 2 4 6 8 10 12 1 3 5 7 9 11 13
この順列がどのように発生するかについて、いくつかの有用な観察結果があります。まず、最初の要素がこの順列で移動しないことに注意してください。偶数インデックスの要素は配列の前に表示されるはずであり、最初の偶数インデックスの要素であるためです。次に、この順列では最後の要素が移動しないことに注意してください。これは、奇数インデックスの要素が配列の最後になるはずであり、それが最後の奇数インデックスの要素であるためです。
これら 2 つの観察結果をまとめると、配列の要素を目的の方法で並べ替えたい場合、実際には配列全体から構成される部分配列を並べ替えて、最初と最後の要素を削除するだけでよいことを意味します。したがって、今後は、純粋に中間要素の並べ替えの問題に焦点を当てます。その問題を解決できれば、全体的な問題は解決したことになります。
では、配列の中央の要素だけを見てみましょう。上記の例から、次のような配列から始めることを意味します。
Element 1 2 3 4 5 6 7 8 9 10 11 12
Index 1 2 3 4 5 6 7 8 9 10 11 12
配列を次のように表示します。
Element 2 4 6 8 10 12 1 3 5 7 9 11
Index 1 2 3 4 5 6 7 8 9 10 11 12
この配列は、インデックスが 0 の配列から最初と最後の要素を切り取ることによって形成されているため、これをインデックスが 1 つの配列として扱うことができます。これは今後非常に重要になるので、必ず覚えておいてください。
では、この順列を生成するにはどうすればよいのでしょうか? まず、各要素を見て、それがどこで始まりどこで終わったかを把握することは問題ありません。その場合、次のように書き出すことができます。
このリストを見ると、いくつかのパターンを見つけることができます。まず、すべての偶数要素の最終インデックスは、常にその要素の半分の位置にあることに注意してください。たとえば、位置 4 の要素は位置 2 になり、位置 12 の要素は位置 6 になるなどです。これは理にかなっています。すべての偶数要素を配列の先頭にプッシュしたため、要素の半分が彼らが追い出され、邪魔にならないように移動される前に来ました。
では、奇数要素はどうでしょうか。さて、全部で12個の要素があります。奇数番号の各要素は後半にプッシュされるため、位置 2k+1 の奇数番号の要素は少なくとも位置 7 にプッシュされます。後半内のその位置は k の値によって与えられます。したがって、奇数位置 2k+1 の要素は、位置 7 + k にマップされます。
このアイデアを一般化するのに少し時間がかかります。並べ替える配列の長さが 2n であるとします。位置 2x の要素は位置 x にマップされ (ここでも、偶数は半分になります)、位置 2x+1 の要素は位置 n + 1 + x にマップされます。これを言い換えると：
位置 p の要素の最終的な位置は、次のように決定されます。
- ある整数 x に対して p = 2x の場合、2x ↦ x
- ある整数 x に対して p = 2x+1 の場合、2x+1 ↦ n + 1 + x
そして今、私たちは完全にクレイジーで予想外のことをしようとしています。現時点では、各要素がどこで終了するかを決定するための区分規則があります。2 で割るか、n + 1 を含む何か奇妙なことを行います。ただし、数論の観点からは、どこで終了するかを説明する単一の統一規則があります。すべての要素が終了するはずです。
必要な洞察は、どちらの場合も、何らかの形でインデックスを 2 で割っているように見えるということです。偶数の場合、新しいインデックスは実際には 2 で除算するだけで形成されます。奇妙なケースとして、新しいインデックスは 2 で割ることによって形成されているように見えますが ( 2x +1 が x + (n + 1) になることに注意してください)、そこには余分な項があります。ただし、数論的な意味では、これらは両方とも実際には 2 による除算に対応します。理由は次のとおりです。
ソースインデックスを取得して 2で割って宛先インデックスを取得するのではなく、宛先インデックスを取得して 2を掛けるとどうなるでしょうか。すると、面白いパターンが浮かび上がります。
元の数が 2x だったとします。宛先は x であり、宛先インデックスを 2 倍にして 2x を取得すると、ソース インデックスになります。
元の数が 2x+1 だったとします。宛先は n + 1 + x です。では、宛先インデックスを 2 倍にするとどうなるでしょうか。これを行うと、2n + 2 + 2x が返されます。これを並べ替えると、(2x+1) + (2n+1) と書き換えることができます。つまり、元のインデックスに加えて、余分な (2n+1) 項が返されます。
ここでキッカーとして、すべての演算が 2n + 1 を法として行われるとどうなるでしょうか? その場合、元の数が 2x + 1 だった場合、宛先インデックスの 2 倍は (2x+1) + (2n+1) = 2x + 1 (モジュロ 2n+1) です。つまり、デスティネーション インデックスは実際にはソース インデックスの半分であり、モジュロ 2n+1 で計算されます!
これにより、非常に興味深い洞察が得られます。2n 要素の配列の各要素の最終的な目的地は、その数を 2 で割って 2n+1 を法として得られます。これは、すべてがどこに行くかを決定するための優れた統一されたルールがあることを意味します。2n+1 を法として 2 で割ることができればよいだけです。たまたま、偶数の場合、これは通常の整数除算であり、奇数の場合、n + 1 + x の形式をとることがわかります。
したがって、問題を次のように再構成できます。2n 要素の 1 インデックス配列が与えられた場合、元はインデックス x にあった各要素が位置 x/2 mod (2n+1 )?
この時点で、私たちはかなりの進歩を遂げました。任意の要素が与えられた場合、その要素がどこに到達するかを知っています。順列全体のサイクル分解を取得する良い方法を見つけられれば、完了です。
残念ながら、これは物事が複雑になるところです。たとえば、配列に 10 個の要素があるとします。その場合、配列を次のように変換します。
Initial: 1 2 3 4 5 6 7 8 9 10
Final: 2 4 6 8 10 1 3 5 7 9
この順列のサイクル分解は (1 6 3 7 9 10 5 8 4 2) です。配列に 12 個の要素がある場合、次のように変換します。
Initial: 1 2 3 4 5 6 7 8 9 10 11 12
Final: 2 4 6 8 10 12 1 3 5 7 9 11
これには循環分解があります (1 7 10 5 9 11 12 6 3 8 4 2 1)。配列に 14 個の要素がある場合、次のように変換します。
Initial: 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Final: 2 4 6 8 10 12 14 1 3 5 7 9 11 13
これは、サイクル分解 (1 8 4 2)(3 9 12 6)(5 10)(7 11 13 14) を持ちます。配列に 16 個の要素がある場合、次のように変換します。
Initial: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Final: 2 4 6 8 10 12 14 16 1 3 5 7 9 11 13 15
これは循環分解 (1 9 13 15 16 8 4 2)(3 10 5 11 14 7 12 6) を持っています。
ここでの問題は、これらのサイクルが予測可能なパターンに従っていないように見えることです。この問題を O(1) 空間と O(n) 時間で解こうとすると、これは実際の問題です。個々の要素が与えられたとしても、それがどのサイクルに含まれているかを把握でき、そのサイクルを効率的にシャッフルできますが、どの要素がどのサイクルに属しているか、異なるサイクルがいくつあるかなどをどのように把握するかは明確ではありません.
ここで数論の出番です。各要素の新しい位置は、その数を 2 で割って 2n+1 を法として形成されることを思い出してください。これを逆に考えると、2n+1 を法として 2を掛けることで、各数値の代わりになる数値を計算できます。したがって、循環分解を逆に見つけることでこの問題を考えることができます。数値を選び、それを 2 で乗算し続け、2n+1 で modding し、循環が完了するまで繰り返します。
これにより、よく研究された問題が生じます。数 k から始めて、数列 k、2k、2 2 k、2 3 k、2 4 k などを考えるとします。これらはすべて 2n+1 を法として行われます。これを行うと、改造している奇数 2n+1 に応じて異なるパターンが得られます。これは、上記のサイクル パターンが幾分恣意的に見える理由を説明しています。
誰かがこれをどのように考え出したかはわかりませんが、ある数 k に対して3 kを法とするこのパターンを取るとどうなるかについて、数論から美しい結果が得られることがわかりました。
定理:シーケンス 3 s、 3 s ·2、 3 s ·2 2、 3 s ·2 3、 3 s ·2 4などを考えてみましょう。これらはすべて、一部の k ≥ s に対して3 kを法とします。このシーケンスは、3 sで割り切れるが 3 s+1で割り切れない 1 から 3 kまでのすべての数を循環します。
いくつかの例でこれを試すことができます。モジュロ 27 = 3 2で作業してみましょう。定理によると、3、3 · 2、3 · 4 などをすべてモジュロ 27 で見ると、3 で割り切れるが 9 では割り切れない 27 未満のすべての数が表示されるはずです。私たちが得るもの：
最終的に 3、6、12、15、21、24 が表示されましたが (この順序ではありません)、これらは実際には 27 未満で 3 で割り切れるが 9 では割り切れないすべての数です。
また、この作業 mod 27 を試して、1、2、2 2、2 3、2 4 mod 27 を考慮すると、1 で割り切れるが 3 で割り切れない 27 未満のすべての数が表示されるはずです。つまり、これにより、3 で割り切れない 27 未満のすべての数値が返されます。これが正しいかどうかを見てみましょう。
これらを並べ替えると、1、2、4、5、7、8、10、11、13、14、16、17、19、20、22、23、25、26 の数字が返されました (ただし、この順序ではありません)。 . これらは、3 の倍数ではない 1 から 26 までの数字です。
この定理は、次の理由でアルゴリズムにとって重要です。ある数 k に対して 2n+1 = 3 kの場合、1 を含むサイクルを処理すると、3 の倍数ではないすべての数が適切にシャッフルされます。3 でサイクルを開始すると、3 で割り切れるが 9 で割り切れないすべての数が適切にシャッフルされます。9 でサイクルを開始すると、9 で割り切れるが 27 で割り切れないすべての数が適切にシャッフルされます。より一般的に言えば、1、3、9、27、81 などの数字に対してサイクル シャッフル アルゴリズムを使用すると、配列内のすべての要素を 1 回だけ適切に再配置するので、何かを見落としたことを心配する必要はありません。
では、これがどのように 3 k + 1 につながるのでしょうか? そうですね、2n + 1 = 3 kが必要なので、2n = 3 k - 1 が必要です。しかし、これを行ったときに、配列の最初と最後の要素を削除したことを思い出してください。これらを再度追加すると、この手順が正しく機能するにはサイズ3 k + 1のブロックが必要であることがわかります。ブロックがこのサイズである場合、サイクル分解が 1 を含むサイクル、3 を含む重複しないサイクル、9 を含む重複しないサイクルなどで構成され、これらのサイクルが配列のすべての要素を含むことが確実にわかります。 . したがって、1、3、9、27 などのサイクルを開始するだけで、完全に保証されます。すべてが正しくシャッフルされます。すごい！
そして、なぜこの定理は正しいのでしょうか? 1、k、k 2、k 3などの数 kが p の倍数ではないすべての数を巡回する (p が素数であると仮定して) mod p nである数 k は、の原始根と呼ばれます。数 p n。2 はすべての数 k に対する 3 kの原始根であるという定理があるため、このトリックが機能します。時間があれば、この回答を編集してこの結果の証明を含めたいと思いますが、残念ながら私の数論はこれを行う方法を知っているレベルではありません。
この問題は、取り組むのがとても楽しかったです。奇数を法とする 2 で割る、循環分解、原始根、および 3 のべき乗によるかわいいトリックが含まれます。私はこの arXiv の論文にお世話になっています。この論文は、同様の (ただしまったく異なる) アルゴリズムを説明しており、この手法の背後にある重要なトリックを理解してくれました。それにより、説明したアルゴリズムの詳細を理解することができました。
お役に立てれば！
これは、templatetypedef の回答に欠けている数学的引数のほとんどです。（残りは比較的退屈です。）
補題: すべての整数 に対してk >= 1、 があり
2^(2*3^(k-1)) = 1 + 3^k mod 3^(k+1)ます。
証明: の帰納法によるk.
基本ケース ( k = 1): あり2^(2*3^(1-1)) = 4 = 1 + 3^1 mod 3^(1+1)ます。
帰納的な場合 ( k >= 2): if 2^(2*3^(k-2)) = 1 + 3^(k-1) mod 3^k, then q = (2^(2*3^(k-2)) - (1 + 3^(k-1)))/3^k.
2^(2*3^(k-1)) = (2^(2*3^(k-2)))^3
= (1 + 3^(k-1) + 3^k*q)^3
= 1 + 3*(3^(k-1)) + 3*(3^(k-1))^2 + (3^(k-1))^3
+ 3*(1+3^(k-1))^2*(3^k*q) + 3*(1+3^(k-1))*(3^k*q)^2 + (3^k*q)^3
= 1 + 3^k mod 3^(k+1).
定理: すべての整数i >= 0およびk >= 1に対して、 が
存在し、2^i = 1 mod 3^kその場合のみi = 0 mod 2*3^(k-1)
証明: “if” の方向は Lemma から導かれます。なら
i = 0 mod 2*3^(k-1)、
2^i = (2^(2*3^(k-1)))^(i/(2*3^(k-1)))
= (1+3^k)^(i/(2*3^(k-1))) mod 3^(k+1)
= 1 mod 3^k.
「その場合のみ」の方向は の誘導によるものkです。
基本ケース ( k = 1): if i != 0 mod 2、 then i = 1 mod 2、および
2^i = (2^2)^((i-1)/2)*2
= 4^((i-1)/2)*2
= 2 mod 3
!= 1 mod 3.
帰納的な場合 ( k >= 2): if 2^i = 1 mod 3^k、 then
2^i = 1 mod 3^(k-1)、および帰納的な仮説はそれを意味し
i = 0 mod 2*3^(k-2)ます。しましょうj = i/(2*3^(k-2))。補題により、
1 = 2^i mod 3^k
= (1+3^(k-1))^j mod 3^k
= 1 + j*3^(k-1) mod 3^k,
(3^(k-1))^2ここで、削除された項は、 so
j = 0 mod 3、および で割り切れi = 0 mod 2*3^(k-1)ます。