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

フィッシャー–イェーツのシャッフル  は、有限集合からランダムな順列を生成するアルゴリズムである。言い換えると、有限列をランダムな別の順序の有限列に並べ直す方法である。この名前はロナルド・フィッシャーおよびフランク・イェーツから名付けられた。また、クヌースのシャッフルとも呼ばれる。フィッシャー–イェーツのシャッフルは、全ての順列の組み合わせが等しく存在しうるため、偏りがない。このアルゴリズムの改良されたバージョンはさらに効果的であり、処理時間はシャッフルされる要素数に比例するのみで、余分な時間はかからず、また追加の保持領域を必要としない。フィッシャー–イェーツのシャッフルの派生にサットロのアルゴリズムがあり、こちらは長さ //n// のランダムな円順列を生成する。

フィッシャー–イェーツのシャッフルは、帽子に入れた数字の書かれたくじをなくなるまで取り出して並べていく手順に似ている。

1. フィッシャーとイェーツによるアルゴリズム
-----------------------

このアルゴリズムのオリジナルの手法は、1938年、フィッシャーとイェーツによって //Statistical tables for biological, agricultural and medical research// に記述された。このアルゴリズムは紙とペンを使うことを想定しており、ランダム選択には乱数表を用いる。1から //N// までのランダムな順列を得る基本的な手順を以下に示す。

1 から //N// までの数字を書く。
まだ消されてない数字の数を数え、1 からその数以下までのランダムな数字 //k// を選ぶ。
残っている数字から //k// 番目の数字を消し、別の場所にその数字を書き出す。
すべての数字が消されるまで手順 2, 3 を繰り返す。
手順3で書かれた数列が元の数値からのランダム順列となる。結果の順列を真にランダムで、かつ偏りがないものにするためには、手順2で抽出される数字もまた真にランダムで、かつ偏りがないものでなければならない。フィッシャーとイェーツは、乱数表から必要な範囲内の数字を選び出す際に、いかなる偏りも避けるようにする方法について注意深く記述している。彼らはまた、1から //N// までのランダムな数字を選択し、重複した場合は除く、といったシンプルな方法で順列の半分を生成したのち、重複することが多くなるであろう残りの半分を、より複雑なアルゴリズムで生成する方法を示している。

2. 改良されたアルゴリズム
--------------

フィッシャー–イェーツのシャッフルの改良されたバージョンはコンピュータの使用を想定している。それはリチャード・ダステンフェルドによって1964年に紹介され、ドナルド・クヌースもまた//The Art of Computer Programming//において"Algorithm P"として世に広めた。ダステンフェルド、クヌースともに、著書の初版ではフィッシャーとイェーツの研究については、おそらく気づいていなかったために紹介していない。//The Art of Computer Programming//の続版ではフィッシャーとイェーツの業績について言及している。

ダステンフェルドのアルゴリズムとフィッシャー–イェーツのそれには、小さいが決定的な差異が存在する。フィッシャー–イェーツの手法を単純にコンピュータで実装する場合、上記の手順3において、残っている数を数え上げるという不要な時間を要する。対してダステンフェルドの手法では「消す」数字を、残っている数字の中で最後の数字と入れ替え、数列の最後に移動させる。これにより、計算量はフィッシャー–イェーツ版の単純な実装の場合の//O//と比べ、//O//に減少する。この変更により、アルゴリズムは下記のようになる。ここでは0始まりの配列を使用する。

要素数が //n// の配列 //a// をシャッフルする://i// を //n// - 1 から 1 まで減少させながら、以下を実行する//j// に 0 以上 //i// 以下のランダムな整数を代入する//a//[//j//] と //a//[//i//]を交換する

パラメータ //p//, //q// に対して //p// 以上 //q// 未満のランダムな整数を返す乱数生成器を使用する場合、配列を上記の例と反対方向に走査する以下のアルゴリズムを用いることができる。 要素数が //n// の配列 //a// をシャッフルする://i// を 0 から //n// - 2 まで増加させながら、以下を実行する//j// に //i// 以上 //n// 未満のランダムな整数を代入する//a//[//j//] と //a//[//i//]を交換する

3. 「取り出し」アルゴリズム
---------------

ダステンフェルドによって実装されたフィッシャー–イェーツのシャッフルは「内部でのシャッフル」である。これは、与えられた初期化済みの配列の要素を、その配列内でシャッフルする。シャッフルされた配列を別に生成することはない。配列が1本あればアルゴリズムを実行できるため、シャッフルされる配列のサイズが大きく、省メモリの要求がある場合は「内部でのシャッフル」の方が優れているだろう。

配列の初期化とシャッフルを併せて行う場合には、「取り出し」版のシャッフルを使うことで、メモリの使用量は2倍に増えるが、少しだけ計算速度を速めることができる。このやり方では、配列を元配列と生成配列の2本を用意し、配列の添字 //i// を増やしながら処理を行う。まず生成配列の //i// 番目に、配列の初めから //i// までの中でのランダムな場所 //j// 番目の値を移動し、その後に元配列の //i// 番目の値を、生成配列の //j// 番目に代入する。//i// と //j// は同じになることもあり、この場合、初期化されていない値を「移動する」ことが起こりうるが、その値はすぐに上書きされるため問題はない。生成配列を個別に初期化する必要はなく、交換処理も必要ない。「元配列」の値が、例えば0から //n// - 1 までの整数のような、シンプルに求められる場合であれば、「元配列」を変更することがないため、関数などに置き換えることもできる。計算速度の改善を計算量理論的に言えば、オーダーを変えず、係数を改善するだけであるので、計算方法を極限まで最適化する必要がある場合に意味を成すと言える。

要素数が //n// の配列 //a// を、配列 //source// をランダムにシャッフルしたコピーで初期化する ://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// から取得した値を代入する

4. 例
----

4.1. 紙とペンを使用した場合
----------------

このサンプルでは、1から8までの数字をフィッシャーとイェーツによる手法を用いてシャッフルする。まずはそれらの数字をメモしておく。

1から8までの数字の中でランダムな数字 //k// を取得する。ここでは3とする。その後、メモの中の //k// 番目の数字を消し、その数字を結果に書き出す。今回の例でいえば、3番目の数字の3を処理する。

2回目は1から7までの範囲でランダムな数字を習得する。今回は4だったとする。「まだ消されていない」数字のうち4番目の数字を消し、結果に加える。今回は5が処理されることになる。

次は1から6、その次は1から5というように、消去と書き出しの手順を上記同様に繰り返していく。



4.2. 現在のアルゴリズム
--------------

ここでは同じ例をダステンフェルドの手法で行う。上記の例では数字の消去と書き出しを行ったが、今回は選ばれていない数字の中で最後の数字との入れ替えを行う。前と同様に1から8までの数字をメモしておく。

1から8までの数字の中でランダムな数字を取得する。今回は6だったとする。この場合、6番目と8番目の数字を交換する。

次は1から7までの数字の中でランダムな数字を取得する。2だった場合、2番目と7番目の数字を交換する。

続けて1から6までの数字の中でランダムな数字を取得する。ここで取得した数字が6だった場合、6番目の数字をそのまま結果とする。今回の例で言えば8を結果とする。結果の数列が完成するまで、ここまでの処理を繰り返す。

この時点で処理が終了し、「7 5 4 3 1 8 2 6」という順列が得られる。

5. バリエーション
----------

5.1. サットロのアルゴリズム
----------------

長さ //n// の一様に分布された円順列を生成するアルゴリズムがサンドラ・サットロによって1986年に発表された。ダステンフェルドとサットロのアルゴリズムの違いはたった一つである。上記の手順2において、ランダムな数字 //j// を取得する場合に、その範囲を1以上 //i// − 1 以下にするだけである。この単純な変更によって、結果の順列は常に円順列を構成するようになる。

後述するとおり、フィッシャー–イェーツのシャッフルを実装しようとした場合に、「意図せず」サットロのアルゴリズムを実装してしまうことも多い。この場合は、//n//!通りのすべての順列のパターンではなく、! 通りのパターンから取得してしまうため、結果に偏りが生じてしまう。

サットロのアルゴリズムが常に正しく長さ //n// の円順列のひとつを生成することは、以下のように帰納的に説明できる。ループの1回目が終了したあとに、残りのループが //n//  − 1 個の要素からなる循環を生成するならば、生成された順列は長さ //n// の円順列のひとつとなる。循環とは、開始した位置の要素を位置 //p// へ移動し、位置 //p// にあった要素は新しい場所へ移動し、以後すべての要素が他の場所へと移動した後に、最後の要素が開始した位置へ戻ることを意味する。ここで、サットロのアルゴリズムでのループの1回目で最後の要素と交換された場所を位置 //k// とし、次に交換される場所を位置 //l// とする。そして、すべての要素数 //n// の順列 //π// と //n// − 1 までの順列 //σ// を比較してみると、//π// と //σ// には位置 //k// にたどり着くまでには違いがない。しかし、//π// では位置 //k// にもともとあった要素は位置 //l// ではなく順列の最後に移動する。そしてもともと最後にあった要素は位置 //l// に移動する。これ以降は //π// の位置の手順は //σ// の手順に再び合致することになり、サットロのアルゴリズムは要求されているとおりにすべての場所を処理しながら開始した位置へと戻っていく。

この順列の正しさに関しては、アルゴリズムが ! 通りの独立した順列を生成できること、そして偏りのない乱数を使用した場合に、それらが等確率で生成できることが確認できればそれで十分である。ただし、生成される ! 通りの独立した順列は、長さ //n// の循環集合を完全に排除されている必要がある。このような順列は、//n// が最後にあり、重複のない循環記法を持ち、残りの要素は ! 通りの独立した順列で記述されることができるものである。

以下のサンプルはPythonによるサットロのアルゴリズムの実装例である。

from random import randrange

def sattoloCycle: i = len while i > 1: i = i - 1 j = randrange # 0 <= j <= i-1 items[j], items[i] = items[i], items[j] return<WtXmlEndTag />

6. 他のシャッフルアルゴリズムとの比較
--------------------

フィッシャー–イェーツのシャッフルは極めて効率的であり、時間的空間的な計算量は最適である。偏りのない良質な乱数をもとにするならば、生成結果も偏りがないことが保証される。他のアルゴリズムと比較してもその長所は変わらない。もしも結果の順列の一部のみが必要であれば、必要な数の順列が生成された時点で処理を中断すればよい。

異なるシャッフルの手法としては、集合のそれぞれの要素にランダムな番号を付与し、その後にそれらをソートする方法がある。ソートによる手法は、フィッシャー–イェーツのシャッフルとは時間的計算量は同一である。ただし、一般的なソート法の計算量は //O// であり、効果的に処理するためには時間的計算量が //O// の基数ソートを用いる必要がある。ソートによる手法も、フィッシャー–イェーツのシャッフルと同じく偏りのない結果を生成するが、ランダムな番号を付与する際に重複しないように注意しなければならない。なぜならソートのアルゴリズムは同じ値の要素を並べる際はランダムにならないからである。さらにこの手法では、付与する番号のために空間的計算量 //O// となる追加領域を必要とする。対してフィッシャー–イェーツのシャッフルでは //O// である。ソートによる手法は番号を付与するため、フィッシャー–イェーツのシャッフルとは異なり、並列的な動作を行う。

シャッフルによる手法の派生として、プログラミング言語がサポートしている、ユーザ独自拡張の比較機能を使用して、比較時にランダムな値を返すようにしてシャッフルを行う方法がある。しかし、これは「きわめて悪い方法」であり、この方法は結果がまったく均等に分布せず、ソートのアルゴリズムもきわめて重い。ソートのアルゴリズムにクイックソートを実装されている場合を考える。このとき、はじめに選択されるピボット は固有の要素とする。このアルゴリズムはピボットとその他の要素すべてを比較し、大小を分割し、大小それぞれのグループのサイズによりピボット要素の最終位置が決められる。乱数列が均一に分布されるためには、ピボット要素の最終位置はどの位置にも等しく配置される可能性がなければならない。しかし、はじめの比較において、「より小さい」「より大きい」の判定を等しく行ってしまうため、ピボット要素位置の確率は //p//  = 1/2 の二項分布をとる。つまり、両端よりも中央に近い方に配置されてしまう可能性が高い。マージソートのような違ったソート法でランダムな比較を使用した場合、より均一な結果を取得できることもある。しかしそれも完全ではない。マージソートの場合、二つの数列の中からどちらかの数値を同確率で選択していくことで、その数列を結合する。この「コイントス」のような、2通りからランダムに取得する手法を繰り返す場合、均一な分布となることはない。なぜなら、この方法による、ある順列が生成される確率は2の階乗を分母とする値であるはずであり、求められている確率は 1///n//! となるからである。

そしてこのシャッフル方法は、原理的に無限ループやアクセス違反などのプログラム実行時のエラーを引き起こすことさえある。なぜなら、ソートアルゴリズムがランダムに動作する場合は順序関係