「フィッシャー–イェーツのシャッフル」の版間の差分
編集の要約なし |
|||
| 213行目: | 213行目: | ||
以下のサンプルは[[Python]]によるサットロのアルゴリズムの実装例である。 |
以下のサンプルは[[Python]]によるサットロのアルゴリズムの実装例である。 |
||
< |
<syntaxhighlight lang="python"> |
||
from random import randrange |
from random import randrange |
||
| 223行目: | 223行目: | ||
items[j], items[i] = items[i], items[j] |
items[j], items[i] = items[i], items[j] |
||
return |
return |
||
</syntaxhighlight> |
|||
</source> |
|||
== 他のシャッフルアルゴリズムとの比較 == |
== 他のシャッフルアルゴリズムとの比較 == |
||
2020年7月5日 (日) 23:07時点における版
フィッシャー–イェーツのシャッフル (英: Fisher–Yates shuffle) は、有限集合からランダムな順列を生成するアルゴリズムである。言い換えると、有限列をランダムな別の（シャッフルされた）順序の有限列に並べ直す方法である。この名前はロナルド・フィッシャーおよびフランク・イェーツから名付けられた。また、クヌースのシャッフル(ドナルド・クヌースから)とも呼ばれる。フィッシャー–イェーツのシャッフルは、全ての順列の組み合わせが等しく存在しうるため、偏りがない。このアルゴリズムの改良されたバージョンはさらに効果的であり、処理時間はシャッフルされる要素数に比例するのみで、余分な時間はかからず、また追加の保持領域を必要としない。フィッシャー–イェーツのシャッフルの派生にサットロのアルゴリズムがあり、こちらは長さ n のランダムな円順列を生成する。
フィッシャー–イェーツのシャッフルは、帽子に入れた数字の書かれたくじ（組合せ数学的に区別可能なもの）をなくなるまで取り出して並べていく手順に似ている。
フィッシャーとイェーツによるアルゴリズム
このアルゴリズムのオリジナルの手法は、1938年、フィッシャーとイェーツによって Statistical tables for biological, agricultural and medical research に記述された[1]。このアルゴリズムは紙とペンを使うことを想定しており、ランダム選択には乱数表を用いる。1から N までのランダムな順列を得る基本的な手順を以下に示す。
- 1 から N までの数字を書く。
- まだ消されてない数字の数を数え、1 からその数以下までのランダムな数字 k を選ぶ。
- 残っている数字から k 番目の数字を消し、別の場所にその数字を書き出す。
- すべての数字が消されるまで手順 2, 3 を繰り返す。
- 手順3で書かれた数列が元の数値からのランダム順列となる。
結果の順列を真にランダムで、かつ偏りがないものにするためには、手順2で抽出される数字もまた真にランダムで、かつ偏りがないものでなければならない。フィッシャーとイェーツは、乱数表から必要な範囲内の数字を選び出す際に、いかなる偏りも避けるようにする方法について注意深く記述している。彼らはまた、1から N までのランダムな数字を選択し、重複した場合は除く、といったシンプルな方法で順列の半分を生成したのち、重複することが多くなるであろう残りの半分を、より複雑なアルゴリズムで生成する方法を示している。
改良されたアルゴリズム
フィッシャー–イェーツのシャッフルの改良されたバージョンはコンピュータの使用を想定している。それはリチャード・ダステンフェルドによって1964年に紹介され[2]、ドナルド・クヌースもまたThe Art of Computer Programmingにおいて"Algorithm P"として世に広めた[3]。ダステンフェルド、クヌースともに、著書の初版ではフィッシャーとイェーツの研究については、おそらく気づいていなかったために紹介していない。The Art of Computer Programmingの続版ではフィッシャーとイェーツの業績について言及している[4]。
ダステンフェルドのアルゴリズムとフィッシャー–イェーツのそれには、小さいが決定的な差異が存在する。フィッシャー–イェーツの手法を単純にコンピュータで実装する場合、上記の手順3において、残っている数を数え上げるという不要な時間を要する。対してダステンフェルドの手法では「消す」数字を、残っている数字の中で最後の数字と入れ替え、数列の最後に移動させる。これにより、計算量はフィッシャー–イェーツ版の単純な実装の場合のO(n2)と比べ、O(n)に減少する[5]。この変更により、アルゴリズムは下記のようになる。ここでは0始まりの配列を使用する。
要素数が n の配列 a をシャッフルする(添字は0からn-1):
i を n - 1 から 1 まで減少させながら、以下を実行する
j に 0 以上 i 以下のランダムな整数を代入する
a[j] と a[i]を交換する
パラメータ p, q に対して p 以上 q 未満のランダムな整数を返す乱数生成器を使用する場合、配列を上記の例と反対方向に走査する以下のアルゴリズムを用いることができる。
要素数がnの配列aをシャッフルする(添字は0からn-1):
i を 0 から n - 2 まで増加させながら、以下を実行する
j に i 以上 n 未満のランダムな整数を代入する
a[j] と a[i]を交換する
「取り出し」アルゴリズム
ダステンフェルドによって実装されたフィッシャー–イェーツのシャッフルは「内部でのシャッフル」である。これは、与えられた初期化済みの配列の要素を、その配列内でシャッフルする。シャッフルされた配列を別に生成することはない。シャッフルされる配列のサイズが大きい場合は「内部でのシャッフル」の方が優れているだろう。
配列の初期化とシャッフルを同時に行う場合であれば、「取り出し」版のシャッフルを使うことで少し効率よく行うことができる。このやり方では、配列の添字 i を増やしながら処理を行う。まず生成配列の i 番目に、配列の初めから i までの中でのランダムな場所 j 番目の値を移動し、その後に元配列の i 番目の値を、生成配列の j 番目に代入する。i と j は同じになることもあり、この場合、初期化されていない値を「(同じ場所に)移動する」ことが起こりうるが、その値はすぐに上書きされるため問題はない。生成配列を個別に初期化する必要はなく、交換処理も必要ない。「元配列」の値が、例えば0から n - 1 までの整数のような、シンプルに求められる場合であれば、「元配列」を変更することがないため、関数などに置き換えることもできる。
要素数が n の配列 a を、配列 source をランダムにシャッフルしたコピーで初期化する (配列の添字はともに0から始まる):
i を 0 から n - 1 まで増加させながら、以下を実行する
j に 0 以上 i 以下のランダムな整数を代入する
もしも j と i が等しくないならば
a[i] に a[j] を代入する
a[j] に source[i] を代入する
「取り出し」版のシャッフルが正しいことは以下のように帰納的に確認できる。完全にランダムな数値を生成できるとするならば、n! の異なった乱数を全て一つずつ取得することができる。そうであればすべて異なった順列を生成することができ、それらは完全に一通りずつの順列となる。「j と i が等しくない場合」の処理は、初期化されていない配列の要素に対するアクセスが許容されているプログラミング言語であれば省略することができ、比較してよりコストのかからないアルゴリズムを実行できる。
「取り出し」版のもう一つの利点は、元配列のデータから完全に独立したランダムな要素が取得できるのであれば、元配列の総要素数 n が未知の場合でも使用できる点である。下記の例では配列 a が空の状態でスタートし順番に追加されていく。配列 a の長さは見つけられた要素数をあらわす。
空の配列 a を、要素数が未知の配列 source をランダムにシャッフルしたコピーで初期化する:
source に取得できる値が存在する間、下記を実行する
j に 0 以上「a の要素数」以下のランダムな整数を代入する
もしも j が「a の要素数」と同じならば
a に source から取得した値を追加する
そうでなければ
a に a[j] を追加する
a[j] に source から取得した値を代入する
例
紙とペンを使用した場合
このサンプルでは、1から8までの数字をフィッシャーとイェーツによる手法を用いてシャッフルする。まずはそれらの数字をメモしておく。
| 範囲 | 乱数 | メモ | 結果 |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
1から8までの数字の中でランダムな数字 k を取得する。ここでは3とする。その後、メモの中の k 番目の数字を消し、その数字を結果に書き出す。今回の例でいえば、3番目の数字の3を処理する。
| 範囲 | 乱数 | メモ | 結果 |
|---|---|---|---|
| 1–8 | 3 | 1 2 |
3 |
2回目は1から7までの範囲でランダムな数字を習得する。今回は4だったとする。「まだ消されていない」数字のうち4番目の数字を消し、結果に加える。今回は5が処理されることになる。
| 範囲 | 乱数 | メモ | 結果 |
|---|---|---|---|
| 1–7 | 4 | 1 2 |
3 5 |
次は1から6、その次は1から5というように、消去と書き出しの手順を上記同様に繰り返していく。
| 範囲 | 乱数 | メモ | 結果 |
|---|---|---|---|
| 1–6 | 5 | 1 2 |
3 5 7 |
| 1–5 | 3 | 1 2 |
3 5 7 4 |
| 1–4 | 4 | 1 2 |
3 5 7 4 8 |
| 1–3 | 1 | 3 5 7 4 8 1 | |
| 1–2 | 2 | 3 5 7 4 8 1 6 | |
| 3 5 7 4 8 1 6 2 |
現在のアルゴリズム
ここでは同じ例をダステンフェルドの手法で行う。上記の例では数字の消去と書き出しを行ったが、今回は選ばれていない数字の中で最後の数字との入れ替えを行う。前と同様に1から8までの数字をメモしておく。
| 範囲 | 乱数 | メモ | 結果 |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
1から8までの数字の中でランダムな数字を取得する。今回は6だったとする。この場合、6番目と8番目の数字を交換する。
| 範囲 | 乱数 | メモ | 結果 |
|---|---|---|---|
| 1–8 | 6 | 1 2 3 4 5 8 7 | 6 |
次は1から7までの数字の中でランダムな数字を取得する。2だった場合、2番目と7番目の数字を交換する。
| 範囲 | 乱数 | メモ | 結果 |
|---|---|---|---|
| 1–7 | 2 | 1 7 3 4 5 8 | 2 6 |
続けて1から6までの数字の中でランダムな数字を取得する。ここで取得した数字が6だった場合、6番目の数字をそのまま結果とする。今回の例で言えば8を結果とする。結果の数列が完成するまで、ここまでの処理を繰り返す。
| 範囲 | 乱数 | メモ | 結果 |
|---|---|---|---|
| 1–6 | 6 | 1 7 3 4 5 | 8 2 6 |
| 1–5 | 1 | 5 7 3 4 | 1 8 2 6 |
| 1–4 | 3 | 5 7 4 | 3 1 8 2 6 |
| 1–3 | 3 | 5 7 | 4 3 1 8 2 6 |
| 1–2 | 1 | 7 | 5 4 3 1 8 2 6 |
この時点で処理が終了し、「7 5 4 3 1 8 2 6」という順列が得られる。
バリエーション
サットロのアルゴリズム
長さ n の一様に分布された円順列を生成するアルゴリズムがサンドラ・サットロによって1986年に発表された[6]。ダステンフェルドとサットロのアルゴリズムの違いはたった一つである。上記の手順2において、ランダムな数字 j を取得する場合に、その範囲を1以上 i − 1 以下にするだけである(もとの範囲は1以上 i 以下)。この単純な変更によって、結果の順列は常に円順列を構成するようになる。
後述するとおり、フィッシャー–イェーツのシャッフルを実装しようとした場合に、「意図せず」サットロのアルゴリズムを実装してしまうことも多い。この場合は、n!通りのすべての順列のパターンではなく、(n − 1)! 通りのパターンから取得してしまうため、結果に偏りが生じてしまう。
サットロのアルゴリズムが常に正しく長さ n の円順列のひとつを生成することは、以下のように帰納的に説明できる。ループの1回目が終了したあとに、残りのループが n − 1 個の要素からなる循環を生成するならば、生成された順列は長さ n の円順列のひとつとなる。循環とは、開始した位置の要素を位置 p へ移動し、位置 p にあった要素は新しい場所へ移動し、以後すべての要素が他の場所へと移動した後に、最後の要素が開始した位置へ戻ることを意味する。ここで、サットロのアルゴリズムでのループの1回目で最後の要素と交換された（最後ではない）場所を位置 k とし、次に交換される場所を位置 l とする。そして、すべての要素数 n の順列 π と n − 1 までの順列 σ を比較してみると、π と σ には位置 k にたどり着くまでには違いがない。しかし、π では位置 k にもともとあった要素は位置 l ではなく順列の最後に移動する。そしてもともと最後にあった要素は位置 l に移動する。これ以降は π の位置の手順は σ の手順に再び合致することになり、サットロのアルゴリズムは要求されているとおりにすべての場所を処理しながら開始した位置へと戻っていく。
この順列の正しさに関しては、アルゴリズムが (n − 1)! 通りの独立した順列を生成できること、そして偏りのない乱数を使用した場合に、それらが等確率で生成できることが確認できればそれで十分である。ただし、生成される (n − 1)! 通りの独立した順列は、長さ n の循環集合を完全に排除されている必要がある。このような順列は、n が最後にあり、重複のない循環記法を持ち、残りの要素は (n − 1)! 通りの独立した順列で記述されることができるものである。
以下のサンプルはPythonによるサットロのアルゴリズムの実装例である。
from random import randrange
def sattoloCycle(items):
i = len(items)
while i > 1:
i = i - 1
j = randrange(i) # 0 <= j <= i-1
items[j], items[i] = items[i], items[j]
return
他のシャッフルアルゴリズムとの比較
フィッシャー–イェーツのシャッフルは極めて効率的であり、時間的空間的な計算量は最適である。偏りのない良質な乱数をもとにするならば、生成結果も偏りがないことが保証される。他のアルゴリズムと比較してもその長所は変わらない。もしも結果の順列の一部のみが必要であれば、必要な数の順列が生成された時点で処理を中断すればよい。
異なるシャッフルの手法としては、集合のそれぞれの要素にランダムな番号を付与し、その後にそれらをソートする方法がある。ソートによる手法は、フィッシャー–イェーツのシャッフルとは時間的計算量は同一である。ただし、一般的なソート法の計算量は O(n log n) であり、効果的に処理するためには時間的計算量が O(n) の基数ソートを用いる必要がある。ソートによる手法も、フィッシャー–イェーツのシャッフルと同じく偏りのない結果を生成するが、ランダムな番号を付与する際に重複しないように注意しなければならない。なぜならソートのアルゴリズムは同じ値の要素を並べる際はランダムにならないからである[7]。さらにこの手法では、付与する番号のために空間的計算量 O(n) となる追加領域を必要とする。対してフィッシャー–イェーツのシャッフルでは O(1) である。ソートによる手法は番号を付与するため、フィッシャー–イェーツのシャッフルとは異なり、並列的な動作を行う。
シャッフルによる手法の派生として、プログラミング言語がサポートしている、ユーザ独自拡張の比較機能を使用して、比較時にランダムな値を返すようにしてシャッフルを行う方法がある。しかし、これは「きわめて悪い方法」であり、この方法は結果がまったく均等に分布せず、ソートのアルゴリズムもきわめて重い[8][9][10]。ソートのアルゴリズムにクイックソートを実装されている場合を考える。このとき、はじめに選択されるピボットは固有の要素とする。このアルゴリズムはピボットとその他の要素すべてを比較し、大小を分割し、大小それぞれのグループのサイズによりピボット要素の最終位置が決められる。乱数列が均一に分布されるためには、ピボット要素の最終位置はどの位置にも等しく配置される可能性がなければならない。しかし、はじめの比較において、「より小さい」「より大きい」の判定を等しく行ってしまうため、ピボット要素位置の確率は p = 1/2 の二項分布をとる。つまり、両端よりも中央に近い方に配置されてしまう可能性が高い。マージソートのような違ったソート法でランダムな比較を使用した場合、より均一な結果を取得できることもある。しかしそれも完全ではない。マージソートの場合、二つの数列の中からどちらかの数値を同確率で選択していくことで、その数列を結合する。この「コイントス」のような、2通りからランダムに取得する手法を繰り返す場合、(数列が2よりも大きい場合は)均一な分布となることはない。なぜなら、この方法による、ある順列が生成される確率は2の階乗を分母とする値であるはずであり、求められている確率は 1/n! となるからである。
そしてこのシャッフル方法は、原理的に無限ループやアクセス違反などのプログラム実行時のエラーを引き起こすことさえある。なぜなら、ソートアルゴリズムがランダムに動作する場合は順序関係（例えば推移関係)が正しく提供されないためである[11]。 以前の比較結果に依存するような、確実に結果が予測されうるような比較を行うような振る舞いはソートの手順の中で行われるべきではないが、意図的にこのような比較を行う明確な理由がある場合は別である。例えば、効率化のために、番兵として自分自身との比較を行うような場合は、ランダムな比較関数はこのソートのアルゴリズムを破壊するだろう。
結果が偏る場合の潜在的な要因
フィッシャー–イェーツのシャッフルを実装する場合、アルゴリズム自身の実装および、組み込む乱数の生成方法の両方に注意する必要がある。そうしない場合、結果には検出可能な偏りがあらわれるだろう。以下は偏りが生じる場合の代表的な要因である。
実装上の誤り
フィッシャー–イェーツのシャッフルの実装でよくある誤りは、取得する乱数の範囲を誤ってしまうことである[12]。このとき、欠陥のあるアルゴリズムは正しく動作しているように見えるが、取得可能な順列を等確率で取得することができず、そしてすべての順列を取得することもできない。例えば、上記の例で取得するインデックス j を、よくあるOff-by-oneエラーによってインデックス i よりも1小さい範囲で実行する。その場合、この処理はサットロのアルゴリズムになってしまい、取得できる順列は円順列のみとなる。特にこのアルゴリズムでは、すべての要素は元の位置に配置されることがなくなってしまうのである。
同様に、インデックス j を常に「配列のすべて」から取得する場合もまた、少ないが明確な偏りを生じさせてしまう。これは、交換の回数が nn となり、要素数nの配列が取りうる順列の組み合わせは n! であることによって引き起こされる。nn は n! で割りきれることがない (n > 2 の場合)。これは n − 1 は n の素因数を共有しないためである。割り切れないことによって、いくつかの順列がその他のものよりも多く生成されてしまう。偏りの具体例として、3要素の配列 [1, 2, 3] のシャッフルを行う場合を考える。この配列には6通りの順列が存在する。しかし、今回のアルゴリズムは27通り (33 = 27) のシャッフルを行ってしまう。この27通りのうち、[1, 2, 3]、[3, 1, 2]、[3, 2, 1]は4回あらわれ、残った3種類の順列は5回出現してしまう。
右の図は長さ7の配列をシャッフルしたときに、最終的にどの位置に移動したかを表したものである。ほぼすべての要素において、最終的にもとの位置がもっとも確率が低く、ひとつ後ろの位置がもっとも確率が高くなっている。長さ1000の配列の図も同様に示す。
剰余の偏り
フィッシャー–イェーツのシャッフルでは、一様分布であるランダムな整数を、様々な範囲から取得することが要求される。しかし、ほとんどの乱数生成器においては、それが真の乱数であれ、疑似乱数であれ、決まった範囲からの乱数を提供する。例えば 0 から 232 − 1 までの範囲などである。生成機より得られる乱数を取得したい範囲に絞るための、シンプルかつ一般的な生成方法は、剰余演算を用いる方法である。これは取得した乱数を範囲の大きさで除算し、その余りを取得する。フィッシャー–イェーツのシャッフルにおいては 0–1 から 0–n までの、全ての範囲で等しく乱数を取得することが求められるが、剰余によって求められる乱数は公平に分布せず、余りが小さい方への偏向が生じる場合がある。
例えば、生成器による乱数が、0から99までの範囲で生成される場合を考えよう。このような乱数の取得方法は、乱数表を使用する場合などである。そして今、0から15までの範囲で乱数を取得したいこととする。単純に16で割った余りを使用する場合、0から3までの数字が取得される確率は、他の数字と比べて約17%上昇する。なぜならば、100は16で割り切れないためである。100までの数字の中で、16で割り切れる最大の数字は 6×16 = 96 であり、生成された乱数が96から99となった場合に偏りが生じるのである。この問題を回避する単純な方法は、そのような偏りの生じる数値が生成された場合はその結果を破棄し、適合する範囲の数値が取得できるまで繰り返すことである。最悪のケースを考えれば、永遠に生成と破棄を繰り返す可能性は存在するが、繰り返しの期待回数は1よりも小さくなる。
関連して、乱数生成器が0以上1未満の浮動小数点数を生成される場合の問題を考える。この場合、取得する整数は乱数を範囲の大きさで乗算した後に、小数点以下を切り捨てることで得られる。浮動小数点数による乱数を正しく生成したとしても、その精度には限界があるため、取得したい範囲に正確に分割することができない場合に偏りが生じる。上記の場合と比べると、その偏りは体系的な傾向を示すものではないが、確実に存在する。
例として、基数部が1ビット、指数部が符号付き4ビットの整数で表現される浮動小数点数を考える。このような貧弱な実装は現実には存在しないであろうが、ここでは分かりやすさを優先する。この浮動小数点数は、0以上1未満の範囲では、0から0.125(1/8)単位で0.825(7/8)までの8通りの値をとる。このような浮動小数点数を生成する乱数生成器を使い、0から2までの数値を取得したい場合、乱数に3を掛け、小数点以下を切り捨てる。そのような操作を行ったとき、結果が0または1となる場合がそれぞれ3通りずつ、2となる場合が2通りとなり、2が取得される確率は他の数値よりも低くなる。浮動小数点数の精度が上昇したとしても、取得したい範囲が 2nでなければ偏りが生じてしまう。
疑似乱数生成器の生成範囲、シード値、使用方法に起因される問題
| シード値のビット数 | リストの最大長 |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 3 | 3 |
| 5 | 4 |
| 7 | 5 |
| 10 | 6 |
| 13 | 7 |
| 16 | 8 |
| 24 | 10 |
| 32 | 12 |
| 48 | 16 |
| 64 | 20 |
| 128 | 34 |
| 160 | 40 |
| 226 | 52 |
| 256 | 57 |
| 512 | 98 |
| 1024 | 170 |
| 1600 | 245 |
| 19937 | 2080 |
| 44497 | 4199 |
疑似乱数生成器を使用する場合、初期値によって、生成されていく乱数の並びが完全に決まってしまう。フィッシャー–イェーツのシャッフルを実行する際に、取りうるすべての順列の組み合わせの数が、疑似乱数の初期値の組み合わせよりも多くなる場合にも問題となる。
例えば、多くのプログラミング言語やライブラリで提供されている疑似乱数生成機能は初期値に32ビットの数値をとる。このことは、232通りの数列を生成できることを意味する。ここで、52枚のトランプカードをシャッフルする場合、その取りうる順列の組み合わせの数は52! ≈ 2225.6となるため、232通りではきわめて少ない組み合わせしか取得することができない。初期値に少なくとも226ビットの数値を使用できる乱数生成器でなければ、52枚のカードの山の組み合わせを完全に取得することはできない。
また、もちろんどのような疑似乱数生成器も、初期化時に設定されるシード値の組み合わせを超える、独立した数値の並びを生成することはできない。つまり、1024ビットの初期値を生成できる疑似乱数生成器であっても、シード値が32ビットであれば、 232 通りの独立した順列の組み合わせしか取得することはできない。しかし、初期化と順列の生成の間に、 230通りの乱数をあらかじめ生成し、それをシードとすることによって、とても非効率ではあるが、乱数の組み合わせを増やすことができる。それでも、取得可能な組み合わせは 262 通りにすぎない。
単純な線形合同法による疑似乱数生成器で、上記の「剰余を取得する」方法を使用する場合には特に注意が必要である。線形合同法による乱数生成は、上位ビットと比較すると下位ビットは乱数として劣っている。なぜなら、生成される乱数の下位 n ビットは 2n の周期を持つからである。特に2のべき乗で割って余りを取得する場合、上位ビットを切り捨てることを意味し、そのような数値は乱数としては明らかに使えない。これは質の悪い乱数生成器を使用すれば、質の悪いシャッフルしかできないということを示すよい例である。
関連項目
- RC4 配列のシャッフルを元にしたストリーム暗号
- Reservoir sampling Algorithm R はフィッシャー–イェーツのシャッフルの変形
出典
- ^ Fisher, Ronald A.; Yates, Frank (1948) [1938]. Statistical tables for biological, agricultural and medical research (3rd ed.). London: Oliver & Boyd. pp. 26–27. OCLC 14222135 注: 第6版 ISBN 0-02-844720-4 はウェブ上での閲覧が可能となっている。 しかし記載されているアルゴリズムはC. R. Raoによって変更されている。
- ^ Durstenfeld, R. (July 1964). “Algorithm 235: Random permutation”. Communications of the ACM 7 (7): 420. doi:10.1145/364520.364540.
- ^ Knuth, Donald E. (1969). Seminumerical algorithms. The Art of Computer Programming. 2. Reading, MA: Addison-Wesley. pp. 139–140. OCLC 85975465
- ^ Knuth (1998). Seminumerical algorithms. The Art of Computer Programming. 2 (3rd ed.). Boston: Addison-Wesley. pp. 145–146. ISBN 0-201-89684-2. OCLC 38207978
- ^ Black, Paul E. (2005年12月19日). “Fisher-Yates shuffle”. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. 2007年8月9日閲覧。
- ^
Wilson, Mark C. (21 June 2004). "Overview of Sattolo's Algorithm" (PDF). In F. Chyzak (ed.) (ed.). INRIA Research Report. Algorithms Seminar 2002-2004. Vol. 5542. summary by Éric Fusy. pp. 105–108. ISSN 0249-6399。
{{cite conference}}:|editor=に無意味な名前が入力されています。 (説明) - ^ “Provably perfect shuffle algorithms”. Oleg Kiselyov (3 Sep 2001). 2013年7月9日閲覧。
- ^ “A simple shuffle that proved not so simple after all”. require ‘brain’ (2007年6月19日). 2007年8月9日閲覧。
- ^ “Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot”. Rob Weir: An Antic Disposition (2010年2月27日). 2010年2月28日閲覧。
- ^ “MS、Webブラウザ選択画面にアルゴリズム上のバグか”. ＠IT 西村賢 (2010年3月1日). 2015年12月8日閲覧。
- ^ “Writing a sort comparison function, redux”. require ‘brain’ (2009年5月8日). 2009年5月8日閲覧。
- ^ Jeff Atwood (December 7, 2007). “The Danger of Naïveté”. Coding Horror: programming and human factors. 2015年12月3日閲覧。
