このアルゴリズムのオリジナルの手法は、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]。
配列の初期化とシャッフルを併せて行う場合には、「取り出し」版のシャッフルを使うことで、メモリの使用量は2倍に増えるが、少しだけ計算速度を速めることができる。このやり方では、配列を元配列と生成配列の2本を用意し、配列の添字 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 から取得した値を代入する
長さ n の一様に分布された円順列を生成するアルゴリズムがサンドラ・サットロによって1986年に発表された[6]。ダステンフェルドとサットロのアルゴリズムの違いはたった一つである。上記の手順2において、ランダムな数字 j を取得する場合に、その範囲を1以上 i − 1 以下にするだけである(もとの範囲は1以上 i 以下)。この単純な変更によって、結果の順列は常に円順列を構成するようになる。
サットロのアルゴリズムが常に正しく長さ n の円順列のひとつを生成することは、以下のように帰納的に説明できる。ループの1回目が終了したあとに、残りのループが n − 1 個の要素からなる循環を生成するならば、生成された順列は長さ n の円順列のひとつとなる。循環とは、開始した位置の要素を位置 p へ移動し、位置 p にあった要素は新しい場所へ移動し、以後すべての要素が他の場所へと移動した後に、最後の要素が開始した位置へ戻ることを意味する。ここで、サットロのアルゴリズムでのループの1回目で最後の要素と交換された（最後ではない）場所を位置 k とし、次に交換される場所を位置 l とする。そして、すべての要素数 n の順列 π と n − 1 までの順列 σ を比較してみると、π と σ には位置 k にたどり着くまでには違いがない。しかし、π では位置 k にもともとあった要素は位置 l ではなく順列の最後に移動する。そしてもともと最後にあった要素は位置 l に移動する。これ以降は π の位置の手順は σ の手順に再び合致することになり、サットロのアルゴリズムは要求されているとおりにすべての場所を処理しながら開始した位置へと戻っていく。
フィッシャー–イェーツのシャッフルの実装でよくある誤りは、取得する乱数の範囲を誤ってしまうことである[12]。このとき、欠陥のあるアルゴリズムは正しく動作しているように見えるが、取得可能な順列を等確率で取得することができず、そしてすべての順列を取得することもできない。例えば、上記の例で取得するインデックス j を、よくあるOff-by-oneエラーによってインデックス i よりも1小さい範囲で実行する。その場合、この処理はサットロのアルゴリズムになってしまい、取得できる順列は円順列のみとなる。特にこのアルゴリズムでは、すべての要素は元の位置に配置されることがなくなってしまうのである。
単純な線形合同法による疑似乱数生成器で、上記の「剰余を取得する」方法を使用する場合には特に注意が必要である。線形合同法による乱数生成は、上位ビットと比較すると下位ビットは乱数として劣っている。なぜなら、生成される乱数の下位 n ビットは 2n の周期を持つからである。特に2のべき乗で割って余りを取得する場合、上位ビットを切り捨てることを意味し、そのような数値は乱数としては明らかに使えない。これは質の悪い乱数生成器を使用すれば、質の悪いシャッフルしかできないということを示すよい例である。
^Fisher, Ronald A.; Yates, Frank (1948) [1938]. Statistical tables for biological, agricultural and medical research (3rd ed.). London: Oliver & Boyd. pp. 26–27. OCLC14222135 注: 第6版 ISBN 0-02-844720-4 はウェブ上での閲覧が可能となっている。 しかし記載されているアルゴリズムはC. R. Rao（英語版）によって変更されている。
^Durstenfeld, R. (July 1964). “Algorithm 235: Random permutation”. Communications of the ACM7 (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. OCLC85975465
^
Knuth (1998). Seminumerical algorithms. The Art of Computer Programming. 2 (3rd ed.). Boston: Addison-Wesley. pp. 145–146. ISBN0-201-89684-2. OCLC38207978
