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

フィッシャー–イェーツのシャッフルアルゴリズム：公平なランダム順列生成

フィッシャー–イェーツのシャッフルは、与えられた要素からランダムな順列（並べ替え）を生成するアルゴリズムです。このアルゴリズムは、ロナルド・フィッシャーとフランク・イェーツによって開発され、ドナルド・クヌースによって「クヌースのシャッフル」としても知られています。

アルゴリズムの特長

公平性: 全ての可能な順列が等しい確率で生成されます。偏りがないため、公正なランダムな並べ替えが必要な場面に適しています。
効率性: 改良されたアルゴリズムは、要素数に比例した処理時間で実行され、追加のメモリ領域を必要としません。

アルゴリズムの流れ（改良版）

改良版のフィッシャー–イェーツのシャッフルは、コンピュータでの実装を想定しています。要素数nの配列をシャッフルする手順は以下の通りです。

1. 配列の最後の要素から順に、要素番号`i`を減らしながらループを繰り返します(i = n-1, n-2, ..., 1)。
2. `i`番目の要素と、0から`i`までの間のランダムな要素番号`j`の要素を入れ替えます。

この操作を繰り返すことで、配列の要素がランダムに並び替えられます。計算量はO(n)と非常に効率的です。

オリジナル版との違い

オリジナル版では、残りの要素の中からランダムに要素を選択していました。これは、残りの要素数を数える必要があり、計算量がO(n²)となっていました。改良版では、最後の要素との交換を行うことで、この余分な計算を省いています。

サットロのアルゴリズム

サットロのアルゴリズムは、フィッシャー–イェーツのシャッフルを拡張したアルゴリズムで、長さnの円順列（環状に並んだ順列）を生成します。改良版と異なるのは、ランダムに選択する要素番号`j`の範囲が`0`から`i-1`までの間である点です。

「取り出し」版のアルゴリズム

「取り出し」版は、別途シャッフル後の配列を用意し、元の配列から要素を取り出して新しい配列に配置していく方法です。メモリ使用量は増えますが、計算速度をわずかに向上させる可能性があります。特に、元の配列の要素数が事前に不明な場合にも有効です。

実装上の注意点と偏りの可能性

フィッシャー–イェーツのシャッフルを実装する際には、以下の点に注意する必要があります。

乱数の質: 真にランダムまたは高品質な疑似乱数を使用する必要があります。低品質な乱数を使うと、生成される順列に偏りが生じます。
剰余の偏り: 乱数の範囲を絞る際に剰余演算を使うと、偏りが生じる可能性があります。適切な手法で範囲を絞る必要があります。
インデックスの範囲: ランダムに選択するインデックスの範囲を間違えると、サットロのアルゴリズムになってしまったり、他の偏りが生じたりします。
疑似乱数生成器の特性: 疑似乱数生成器の初期値、シード値、周期などに注意が必要です。生成できる順列の数が少ないと、偏りが生じます。

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

フィッシャー–イェーツのシャッフルは、時間計算量と空間計算量の両面で非常に効率的です。他のシャッフルアルゴリズム（例えば、ランダムな数値を付与してソートする方法）と比較しても、その優位性は変わりません。

しかし、ソートを用いた方法は並列処理に向いているという利点があります。一方、ランダムな比較を行うソートアルゴリズムは、結果に強い偏りが生じ、極めて非効率的になる可能性があるため注意が必要です。

結論

フィッシャー–イェーツのシャッフルは、公平で効率的なランダム順列生成アルゴリズムです。しかし、実装の際には乱数の質やインデックスの範囲などに注意し、偏りが生じないように注意深く実装する必要があります。様々な派生アルゴリズムが存在し、それぞれの用途に最適なアルゴリズムを選択することが重要です。

もう一度検索