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

この例では、フィッシャーとイェーツのオリジナルの方法を用いて、アルファベット順の文字から始めて、AからHまでの文字を並べ替えます。

1から8までの乱数jが選択されます。例えば、 j =3の場合、メモ帳の3番目の文字を消して、それを結果として書き留めます。

2つ目の乱数（今回は1から7まで）が選ばれます。もしその数が4であれば、メモ帳からまだ消されていない4番目の文字を消して、結果に加えます。

次の乱数は1から6の中から選ばれ、次に1から5の中から選ばれ、以下同様に、常に上記と同様の消去法を繰り返します。

デュルステンフェルドのアルゴリズムでは、選択された文字を消して別の場所にコピーする代わりに、まだ選択されていない最後の文字と入れ替えます。これまでと同様に、AからHまでの文字から始めます。

1から8までの乱数jを選択し、j番目と8番目の文字を入れ替えます。例えば、乱数が6の場合、リストの6番目と8番目の文字を入れ替えます。

次に1から7までの乱数が選択され、選択された文字が7番目の文字と入れ替わります。例えば、2が選ばれた場合は、2番目と7番目の文字を入れ替えます。

順列が完了するまで、このプロセスが繰り返されます。

8つのステップの後、アルゴリズムは完了し、結果として得られる順列はGEDCAHB Fとなります。

非常によく似たアルゴリズムが、1986 年にSandra Sattoloによって、 (最大) 長さnの一様分布サイクルを生成するために発表されました。^{[ 8 ] [ 9 ]} Durstenfeld のアルゴリズムと Sattolo のアルゴリズムの唯一の違いは、後者では、上記のステップ 2 で、乱数jが 1 からi − 1までの範囲(1 からiまでの範囲ではなく) から選択されることです。この単純な変更により、結果として得られる順列が常に単一のサイクルで構成されるようにアルゴリズムが変更されます。  

実際、後述するように、通常のフィッシャー・イェーツシャッフルを意図しているにもかかわらず、誤ってサットロのアルゴリズムを実装してしまうことは非常に容易です。これにより、 n !通りの可能な順列の完全なセットからではなく、 ( n  -  1)! 通りの長さのサイクルのより小さなセットから順列が選択されるため、結果に偏りが生じます。

サットロのアルゴリズムが常に長さnのサイクルを生成するという事実は、帰納法によって示すことができます。帰納法によって、ループの最初の反復の後、残りの反復では最初のn  − 1 個の要素が長さn − 1 のサイクルに従って置換されると仮定します (これらの残りの反復は、最初のn − 1 個の要素にサットロのアルゴリズムを適用したものです)。これは、最初の要素を新しい位置pまで追跡し、次に位置pにあった要素を新しい位置まで追跡し、といったように、他のすべての位置を訪れた後で初めて最初の位置に戻ることを意味します。最初の反復で最後の要素が (最終ではない) 位置kにある要素と交換され、その後の最初のn − 1 個の要素の置換がそれを位置lに移動したとします。すべてのn個の要素の置換πと、最初のn − 1 個の要素の残りの置換σを比較します。前述のように連続する位置を追跡すると、位置kに到達するまでπとσの間に違いはありません。しかし、 πの場合、元々位置kにあった要素は位置lではなく最終位置に移動し、元々最終位置にあった要素は位置lに移動します。そこから先は、 πの位置のシーケンスは再びσのシーケンスに従い、要求どおり、初期位置に戻る前にすべての位置が訪問されます。                  

順列の確率が等しいことに関しては、修正されたアルゴリズムでは ( n  −  1)! 通りの異なる乱数列が生成され、それぞれが明らかに異なる順列を生成し、乱数源が偏りがないと仮定すると、それぞれが等しい確率で発生することを観察すれば十分である。このようにして生成された ( n  − 1)! 通りの異なる順列は、長さn のサイクルの集合を正確に網羅する。このようなサイクルはそれぞれ、最後の位置に値nを持つ一意のサイクル表記を持ち、残りの値の ( n − 1)! 通りの順列によってサイクル表記の他の位置を埋めることができる。  

PythonにおけるSattoloのアルゴリズムの実装例は以下のとおりです。

from random import randrangedef sattolo_cycle ( items ) -> None : """Sattoloのアルゴリズム。""" i = len ( items ) while i > 1 : i = i - 1 j = randrange ( i ) # 0 <= j <= i-1 items [ j ], items [ i ] = items [ i ], items [ j ]

フィッシャー・イェーツ法に基づいた、いくつかの並列シャッフルアルゴリズムが開発されている。

1990年、アンダーソンは共有メモリにアクセスするプロセッサの数が少ないマシン向けの並列バージョンを開発した。^{[ 10 ]}このアルゴリズムは、ハードウェアが公平に動作する限り、ランダムな順列を均一に生成する。

2015年、BacherらはMERGESHUFFLEというアルゴリズムを発表しました。これは、配列をほぼ等しいサイズのブロックに分割し、Fisher-Yatesを使用して各ブロックをシャッフルし、その後ランダムマージを再帰的に使用してシャッフルされた配列を生成します。^{[ 11 ]}また、2015年には、Shun、Gu、Blelloch、Fineman、およびGibbonsが、元のFisher-Yatesシャッフルを直接並列化して、線形作業と多対数深度の並列アルゴリズムを得る方法を示しました。^{[ 12 ]}

各要素をすべての要素からランダムに選択された別の要素と交換するという単純な方法は偏りがある。^{[ 13 ]}異なる順列は、すべての要素に対して異なる確率で生成される。${\displaystyle n>2}$なぜなら、異なる順列の数、${\displaystyle n!}$アルゴリズムのランダムな結果の数を均等に分割しない、${\displaystyle n^{n}}$特に、ベルトランの公準により、少なくとも1つの素数が存在します。${\displaystyle n/2}$そして${\displaystyle n}$、そしてこの数字は割ります${\displaystyle n!}$しかし分割しない${\displaystyle n^{n}}$。

from random import randrangedef naive_shuffle ( items ) -> None : """素朴なメソッド。これはやってはいけない例です。代わりにフィッシャー・イェーツ法を使用してください。""" n = len ( items ) for i in range ( n ): j = randrange ( n ) # 0 <= j <= n-1 items [ j ], items [ i ] = items [ i ], items [ j ]

別の方法として、シャッフルするセットの各要素に乱数を割り当て、割り当てられた乱数に従ってセットをソートする方法があります。ソート方法は、フィッシャー・イェーツ法と同じ漸近的な時間計算量を持っています。一般的なソートはO ( n  log n ) ですが、基数ソートを使用すると、 O ( n ) の時間で効率的にソートできます。フィッシャー・イェーツ法と同様に、このソート方法も偏りのない結果を生成します。ただし、ソートアルゴリズムは通常、同点の場合に要素をランダムに並べ替えないため、割り当てられた乱数が重複しないように注意する必要があります。^{[ 14 ]}さらに、この方法は漸近的に大きなスペースを必要とします。乱数用にO ( n ) の追加ストレージスペースが必要ですが、フィッシャー・イェーツ法ではO (1 ) のスペースで済みます。最後に、このソート方法は、逐次的なフィッシャー・イェーツ法とは異なり、単純な並列実装が可能です。 

上記の方法の変形として、ユーザー指定の比較関数によるソートをサポートする言語で使用されているものがあり、ランダムな値を返す比較関数でソートしてリストをシャッフルする方法があります。ただし、この方法では、非常に不均一な分布が生じる可能性が高く、さらに使用するソート アルゴリズムに大きく依存します。^{[ 15 ] [ 16 ]} 例えば、クイック ソートをソート アルゴリズムとして使用し、固定要素を最初のピボット要素として選択したとします。アルゴリズムは、ピボットを他のすべての要素と比較し、ピボットより小さい要素と大きい要素に分け、これらのグループの相対的なサイズによってピボット要素の最終的な位置が決まります。均一に分布したランダムな順列の場合、ピボット要素の可能な最終位置はそれぞれ同じ確率であるはずですが、最初の比較のそれぞれが「小さい」または「大きい」を同じ確率で返す場合、その位置はp = 1/2の二項分布となり、シーケンスの中央付近の位置は、端付近の位置よりもはるかに高い確率になります。マージソートなどの他のソート方法にランダム比較関数を適用すると、より均一に見える結果が得られるかもしれませんが、実際にはそうではありません。なぜなら、2 つのシーケンスを、一方のシーケンスが枯渇するまで、等しい確率で繰り返し選択してマージしても、均一分布の結果は得られないからです。代わりに、シーケンスを選択する確率は、そのシーケンスに残っている要素の数に比例する必要があります。実際、等しい確率で 2 方向のランダムイベント ( 「コイン投げ」 ) のみを使用し、それを制限された回数だけ繰り返す方法では、シーケンス (2 個以上の要素) の順列を均一分布で生成することはできません。なぜなら、すべての実行パスの確率は、分母が2 のべき乗である有理数になりますが、各可能な順列に必要な確率 1/ n ! はその形式ではないからです。  

原則として、このシャッフル方法は、無限ループやアクセス違反などのプログラム障害を引き起こす可能性さえあります。なぜなら、ソートアルゴリズムの正しさは、ランダムな値を生成する比較では確実に持たない順序関係の特性（推移性など）に依存する可能性があるからです。 ^{[ 17 ]} 結果が確実に予測できる比較（以前の比較に基づく）を決して実行しないソートルーチンでは、このような動作は発生しないはずですが、意図的にそのような比較を行う正当な理由がある場合があります。たとえば、どの要素もそれ自身と等しいと比較されるという事実は、効率上の理由からそれらを番兵値として使用することを可能にし、その場合、ランダムな比較関数はソートアルゴリズムを壊します。

フィッシャー・イェーツ・シャッフルを実装する際によくある間違いは、乱数の範囲を間違えることです。この欠陥のあるアルゴリズムは正しく動作するように見えるかもしれませんが、すべての可能な順列を等しい確率で生成するわけではなく、特定の順列を全く生成しない場合もあります。たとえば、よくあるオフバイワンエラーとしては、上記の例で交換するエントリのインデックスjを、交換先のエントリのインデックスiより常に厳密に小さい値に選択してしまうことが挙げられます。これにより、フィッシャー・イェーツ・シャッフルはサットロのアルゴリズムに変わり、すべての要素を含む単一のサイクルからなる順列のみが生成されます。特に、この修正により、配列のどの要素も元の位置に戻ることはなくなります。

同様に、すべての反復で有効な配列インデックスの全範囲から常にj を選択する場合も、結果は偏っているが、それほど明白ではない。これは、そうするとn ^{n 個}の異なる可能なスワップのシーケンスが得られるのに対し、n要素の配列の可能な順列はn !個しかないという事実からわかる。n > 2の場合、 n ^{n は}n !で割り切れない(後者はn − 1 で割り切れるが、n − 1 はnと素因数を共有しない) ため、 n ⁿ個のスワップのシーケンスのうち、一部の順列は他の順列よりも多く生成される必要がある。この偏りの具体的な例として、3 要素の配列 [1, 2, 3] をシャッフルしたときの可能な結果の分布を観察する。この配列の可能な順列は 6 通り (3! = 6) だが、アルゴリズムは 27 通りのシャッフルを生成する (3 ³ = 27)。この場合、[1, 2, 3]、[3, 1, 2]、[3, 2, 1]はそれぞれ27回のシャッフルのうち4回で発生し、残りの3つの順列はそれぞれ27回のシャッフルのうち5回で発生します。  

右側の行列は、長さ7のリストの各要素が他の位置に配置される確率を示しています。ほとんどの要素において、元の位置（行列の主対角線）に配置される確率が最も低く、1つ後ろの位置に配置される確率が最も高いことがわかります。

フィッシャー・イェーツ・シャッフルでは、さまざまな範囲から一様分布のランダムな整数を選択します。しかし、ほとんどの乱数生成器（真の乱数生成器か擬似乱数生成器かを問わず）は、0 から RAND_MAX までの固定範囲の数値しか直接提供せず、ライブラリによっては RAND_MAX が 32767 と低い場合もあります。^{[ 18 ]} このような数値を目的の範囲に強制的に収めるシンプルで一般的な方法は、剰余演算子を適用することです。^{[ 19 ]}つまり、数値を範囲のサイズで割って余りを取ります。しかし、フィッシャー・イェーツ・シャッフルでは 0-1 から 0- nまでのすべての範囲で乱数を生成する必要があるため、これらの範囲の一部が乱数生成器の自然な範囲を均等に分割しないことがほぼ確実です。したがって、余りが常に均等に分布するとは限らず、さらに悪いことに、バイアスは体系的に小さな余りに有利になります。^{[ 20 ] [ 20 ]：古典的な剰余（バイアスあり）}

例えば、乱数生成器が 0 から 99 までの数値 (Fisher と Yates の元の表の場合と同様) を生成し、100 個の値があるとします。そして、0 から 15 までの (16 個の値) の偏りのない乱数を得たいとします。単純に数値を 16 で割って余りを取ると、0 から 3 までの数値が他の数値よりも約 17% 多く出現することがわかります。これは、16 が 100 を割り切れないためです。100 以下の 16 の最大の倍数は 6×16 = 96 であり、偏りの原因は不完全な範囲 96 から 99 までの数値です。この問題を解決する最も簡単な方法は、余りを取る前にこれらの数値を破棄し、適切な範囲の数値が出現するまで繰り返し試行することです。^{[ 21 ]} 原理的には、最悪の場合、これは永遠に続く可能性がありますが、期待される再試行回数は常に 1 回未満です。

2018年にダニエル・レミールによって、偏りがなく、高コストな剰余演算をほとんど実行しない、必要な範囲の乱数を取得する方法が説明されました。^{[ 22 ]}

関連する問題は、まずランダムな浮動小数点数（通常は [0,1] の範囲）を生成し、次にそれを目的の範囲のサイズで乗算して切り捨てる実装で発生します。^{[ 20 ] : FP 乗算 (バイアスあり) [ 22 ] : 2}ここでの問題は、ランダムな浮動小数点数は、どれほど注意深く生成されたとしても、常に有限の精度しか持たないということです。これは、任意の範囲で可能な浮動小数点値の数が有限であることを意味し、範囲をこの数を均等に分割しない数のセグメントに分割すると、一部のセグメントは他のセグメントよりも多くの可能な値を持つことになります。結果として生じるバイアスは、前のケースと同じ体系的な下降傾向を示しませんが、それでもバイアスは存在します。

フィッシャー・イェーツシャッフル用の乱数を生成する際に「モジュロバイアス」を排除するための追加コストは、アプローチ（古典的なモジュロ、浮動小数点乗算、またはレミールの整数乗算）、シャッフルする配列のサイズ、および使用する乱数生成器によって異なります。^{[ 20 ]：ベンチマーク...}

フィッシャー・イェーツ・シャッフルを擬似乱数発生器（PRNG）で使用すると、別の問題が発生します。このような発生器が出力する数値のシーケンスは、シーケンスの開始時の内部状態によって完全に決定されるため、このような発生器によって駆動されるシャッフルは、発生器が持つ異なる可能な状態よりも多くの異なる順列を生成することはできません。^{[ 23 ]} 可能な状態の数が順列の数を超える場合でも、数値のシーケンスから順列へのマッピングの不規則な性質により、一部の順列は他の順列よりも頻繁に発生します。したがって、バイアスを最小限に抑えるには、PRNG の状態の数が順列の数を少なくとも数桁上回る必要があります。

例えば、多くのプログラミング言語やライブラリに内蔵されている擬似乱数生成器は、内部状態が32ビットしかない場合が多く、つまり2³²^種類の異なる数列しか生成できません。このような生成器を使って52枚のトランプをシャッフルすると、52! ≈ ^2²²⁵.⁶通りの可能な順列のうち、ごく一部しか生成できません。^{[ 24 ]} 226ビット未満の内部状態を持つ生成器では、52枚のトランプのデッキのすべての可能な順列を生成することは不可能です。

擬似乱数生成器は、初期化時点から、初期化に使用できる異なるシード値の数よりも多くの異なるシーケンスを生成することはできません。^{[ 25 ]} したがって、内部状態が 1024 ビットで、32 ビットのシードで初期化された生成器は、初期化直後には 2 ³²種類の異なる順列しか生成できません。生成器を順列の生成に使用する前に何度も実行すれば、より多くの順列を生成できますが、これは乱数を増やす非常に非効率的な方法です。初期化から順列の生成までの間に、生成器を最大 10 億回 (簡単にするために 2 ³⁰回) 乱数で使用できると仮定しても、可能な順列の数は依然として 2 ⁶²だけです。

単純な線形合同法PRNGを、上記で説明した範囲縮小の除算と剰余を取る方法で使用すると、さらに問題が発生します。ここでの問題は、法2eの線形合同法PRNGの下位ビットが上位ビットよりもランダム性が低いことです。^[ 6 ^{]ジェネレータの}下位nビット自体の周期は最大で2nです^。除数が2のべき乗の場合、剰余を取るということは実質的に上位ビットを捨てることを意味し、結果としてランダム性が著しく低下した値になります。LCGが素数を法とする場合は異なるルールが適用されますが、そのようなジェネレータはまれです。これは、質の低いRNGまたはPRNGは質の低いシャッフルを生成するという一般的なルールの例です。