フィッシャー–イェーツのシャッフル
疑似乱数生成器を使用する場合、初期値によって、生成されていく乱数の並びが完全に決まってしまう。フィッシャー–イェーツのシャッフルを実行する際に、取りうるすべての順列の組み合わせの数が、疑似乱数の初期値の組み合わせよりも多くなる場合にも問題となる。
例えば、多くのプログラミング言語やライブラリで提供されている疑似乱数生成機能は初期値に32ビットの数値をとる。このことは、2通りの数列を生成できることを意味する。ここで、52枚のトランプカードをシャッフルする場合、その取りうる順列の組み合わせの数は52! ≈ 2となるため、2通りではきわめて少ない組み合わせしか取得することができない。初期値に少なくとも226ビットの数値を使用できる乱数生成器でなければ、52枚のカードの山の組み合わせを完全に取得することはできない。
また、もちろんどのような疑似乱数生成器も、初期化時に設定されるシード値の組み合わせを超える、独立した数値の並びを生成することはできない。
このアルゴリズムのオリジナルの手法は、1938年、フィッシャーとイェーツによって Statistical tables for biological, agricultural and medical research に記述された。このアルゴリズムは紙とペンを使うことを想定しており、ランダム選択には乱数表を用いる。1から N までのランダムな順列を得る基本的な手順を以下に示す。
1 から N までの数字を書く。
まだ消されてない数字の数を数え、1 からその数以下までのランダムな数字 k を選ぶ。
残っている数字から k 番目の数字を消し、別の場所にその数字を書き出す。
すべての数字が消されるまで手順 2, 3 を繰り返す。
手順3で書かれた数列が元の数値からのランダム順列となる。
結果の順列を真にランダムで、かつ偏りがないものにするためには、手順2で抽出される数字もまた真にランダムで、かつ偏りがないものでなければならない。フィッシャーとイェーツは、乱数表から必要な範囲内の数字を選び出す際に、いかなる偏りも避けるようにする方法について注意深く記述している。彼らはまた、1から N までのランダムな数字を選択し、重複した場合は除く、といったシンプルな方法で順列の半分を生成したのち、重複することが多くなるであろう残りの半分を、より複雑なアルゴリズムで生成する方法を示している。
ここで、サットロのアルゴリズムでのループの1回目で最後の要素と交換された(最後ではない)場所を位置 k とし、次に交換される場所を位置 l とする。そして、すべての要素数 n の順列 π と n − 1 までの順列 σ を比較してみると、π と σ には位置 k にたどり着くまでには違いがない。しかし、π では位置 k にもともとあった要素は位置 l ではなく順列の最後に移動する。そしてもともと最後にあった要素は位置 l に移動する。これ以降は π の位置の手順は σ の手順に再び合致することになり、サットロのアルゴリズムは要求されているとおりにすべての場所を処理しながら開始した位置へと戻っていく。
この順列の正しさに関しては、アルゴリズムが (n − 1)! 通りの独立した順列を生成できること、そして偏りのない乱数を使用した場合に、それらが等確率で生成できることが確認できればそれで十分である。ただし、生成される (n − 1)! 通りの独立した順列は、長さ n の循環集合を完全に排除されている必要がある。このような順列は、n が最後にあり、重複のない循環記法(英語版)を持ち、残りの要素は (n − 1)! 通りの独立した順列で記述されることができるものである。
以下のサンプルはPythonによるサットロのアルゴリズムの実装例である。