ランダム順列

ランダム順列は、一連のオブジェクト、つまり順列値を持つランダム変数のランダムな順序です。ランダム順列の使用は、運任せのゲームや、符号理論、暗号化、シミュレーションのランダム化アルゴリズムでよく使用されます。ランダム順列の良い例は、標準的なトランプの公平なシャッフルです。これは、理想的には 52 枚のカードのランダム順列です。

ランダム順列の計算

エントリーごとの方法

大きさn の集合のランダム順列を一様ランダムに生成する、すなわちn個の順列のそれぞれが等しく出現する可能性があるようなアルゴリズムの1つは、 1からn （両端を含む）までの整数を一様ランダムに選択し、 n回連続して置換せずにシーケンスを生成し、このシーケンス（x ₁、...、x _n）を順列として解釈することです。

{\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}},

ここでは2 行表記で示されています。

非効率的なブルートフォース方式による非置換サンプリングでは、各ステップで 1 からnまでの数字から選択し、ランダムに選択された数字がすでに選択された数字の繰り返しである場合は、まだ選択されていない数字が選択されるまで選択を再試行します。このような場合、ステップごとの予想される再試行回数は、すでに選択された数字の割合の逆数に比例し、全体の再試行回数はそれらの逆数の合計になるため、これは非効率的なアプローチになります。

このような再試行は、各i番目のステップでx ₁、...、x _{i − 1 が}すでに選択されている場合に、 1 からn − i + 1 (両端を含む)までの間で一様乱数j を選択し、 x _{i を}まだ選択されていない数の中でj番目に大きい数に設定するアルゴリズムを使用することで回避できます。これにより、再試行なしで、各ステップで残りの数の中から一様ランダムに選択されます。

フィッシャー・イェーツのシャッフル

フィッシャー・イェイツ・シャッフルと呼ばれる、再試行なしでn 個のアイテムの順列を一様にランダムに生成する簡単なアルゴリズムは、任意の順列（たとえば、恒等順列）から始めて、位置 0 からn − 2までを調べ（最初の要素のインデックスは 0、最後の要素のインデックスはn − 1 という規則を使用します）、各位置iで、現在そこにある要素を、位置iからn − 1（末尾）までの中からランダムに選択された要素と交換します。このアルゴリズムでは、 n個の要素の任意の順列が正確に 1/ n !の確率で生成され、順列が一様に分布します。

unsigned universe ( unsigned m ); /* 一様分布の 0 <= universe(m) <= m-1 のランダムな整数を返します */   

void initialize_and_permute ( unsigned permutation [], unsigned n ) { unsigned i ; for ( i = 0 ; i <= n -2 ; i ++ ) { unsigned j = i + universe ( n - i ); /* i ≤ j < n となるランダムな整数 */ swap ( permutation [ i ], permutation [ j ]); /* ランダムに選択された要素を permutation[i] と交換します */ } }

uniform()関数が単純にとして実装されている場合random() % (m)、の戻り値の数が m の倍数でない場合は、順列の分布に偏りが生じます。ただし、の戻り値の数がm よりも桁違いに大きい random()場合、この影響は小さくなります。random()

ランダム性テスト

ランダムプロセスのすべての計算実装と同様に、Fisher-Yates シャッフルなどのランダム化アルゴリズムの実装によって生成される分布の品質、つまり実際に生成される分布が目的の分布にどれだけ近いかは、疑似乱数ジェネレータやハードウェア乱数ジェネレータなどの実装におけるランダム性の基盤となるソースの品質に依存します。ランダム順列のランダム性テストは多数あり、たとえばDiehard テストの「重複順列」テストなどがあります。このようなテストの一般的な形式は、分布が理論的にわかっている順列統計を取得し、実装からランダムに生成された順列のセットでのその統計の分布が、真の分布からのその統計の分布に近似するかどうかをテストすることです。