ゲーム百科 · ランダムと並び

Fisher–Yatesシャッフルの仕組み|交換範囲と6通りの並び

シャッフルは動く回数より、すべての並びが同じ確率になる条件が重要です。3要素の6経路から、Fisher–Yatesの交換範囲、自分自身との交換、ランダムソートとの違いを確認できます。

約8分で読めますゲームの仕組み
カードの順序を入れ替える実物のトランプ
カードの順序を入れ替える実物のトランプ · Paul Huxley / CC BY 2.0 · 写真クレジット

Fisher–Yatesシャッフルは、まだ確定していない範囲から一つの位置を選び、末尾と交換して、その場所を一つずつ確定させる手順です。後ろから進める形では、現在の位置iに対して交換相手jを0からiまでの範囲から選びます。自分自身の位置も選択肢に含みます。

A・B・Cの3要素なら、最初は3択、次は2択で、6本の選択経路が6通りの並びへ一つずつ対応します。それぞれの選択が均等なら一つの並びは1/6です。よく動いたように見えることと、すべての並びが等確率であることは分けて考えます。

シャッフルの目標は、すべての並びを同じ確率へそろえること

異なる3枚のA・B・Cを並べる方法は6通りです。公平なシャッフルを考える場合は、見た目がよく動いたかではなく、その6通りが同じ確率で得られるかを問います。

要素数並びの数すべて等確率なら1通りの確率
22×1=21/2
33×2×1=61/6
44×3×2×1=241/24

順番が違えば別の並びとして数える

ABCとACBは、含まれる3枚が同じでも別の並びです。最初の位置は3通り、次は残り2通り、最後は1通りなので、全部で3×2×1=6通りになります。要素そのものと、その位置の組合せを分けて考えます。

Aが先頭になる確率だけが同じでも、全体の6通りが等確率とは限りません。ある位置に各要素が同じ回数出ることと、すべての並び全体が均等であることは異なる条件です。シャッフルの目的を部分的な集計だけへ縮めないことが大切です。

同じ並びがもう一度出ることも正しい

ABCをシャッフルした結果がABCのままでも、それだけで失敗とはいえません。元の並びも6通りのうちの一つだからです。元と違う結果だけを許すと、元の並びの確率を0へ変え、すべての並びを同じ確率にする条件から外れます。

「必ず動く」「同じ場所に残らない」といった見た目の条件を追加すると、対象としている並びの集合が変わります。何を公平にしたいかを先に決め、その集合に対して等確率かを調べる必要があります。

要素の名前と位置の番号を分ける

配列の位置を0、1、2と呼ぶ場合、A・B・Cはその位置に入っている値です。シャッフルは値を消したり増やしたりするのではなく、位置を入れ替えます。操作の途中でも、含まれる要素の種類と個数は変わらないことが基本です。

同じ文字が複数ある配列では、見た目が同じでも物理的な要素を区別する考え方が必要になる場合があります。まずA・B・Cのようにすべて異なる値で仕組みを確かめると、位置の移動と文字の一致を混同しにくくなります。

未処理の範囲から1つを選んで交換する
各jを等確率で選ぶことが均等なシャッフルの条件です。 図は横にスクロールできます。
カードの順序を入れ替える実物のトランプ
カードの順序を入れ替える実物のトランプ · 写真クレジット

後ろの位置から一つずつ確定させる

後ろから進めるFisher–Yatesの形では、未確定の範囲から一つの位置を等確率で選び、現在の末尾と交換します。交換後の末尾は確定し、次はその一つ前までの範囲を扱います。

iが2ならjは0・1・2から選ぶ

A・B・Cの3要素では、最初の末尾の位置iは2です。交換相手jは0から2までの3通りから選びます。jが0ならCとAを交換しCBA、jが1ならCとBを交換しACB、jが2なら同じ位置なのでABCのままです。

この段階で末尾へ入る要素は、A・B・Cがそれぞれ1/3です。一回の交換で末尾の値を決め、ほかの二つの順序はまだ未確定として残します。末尾が決まった後で、その場所を次の交換相手へ戻さないことが重要です。

次のiは1、選ぶ範囲も0・1へ縮む

次にiを1へ下げ、jを0または1から選びます。未確定の2要素のうち、どちらを位置1へ置くかが1/2で決まります。最後に位置0へ残る値は自動的に決まるため、さらに別の選択をする必要はありません。

選ぶ範囲が狭くなるのは、確定した末尾をもう動かさないためです。毎回0から2までを選ぶ方式に変えると、先に確定したはずの場所が再び動き、同じ証明を使えなくなります。範囲の端がアルゴリズムの条件になります。

自分自身との交換も選択肢に含める

jがiに等しい場合、見た目の並びは動きません。それでも、その場所の値をそこへ残すという必要な選択肢です。自分自身との交換を除くと、その段階で現在の要素が末尾へ残る可能性を失います。

動きがない選択を無駄として勝手に省くと、対象とする並びの集合が変わる場合があります。操作の回数を見た目で減らすことと、同じ確率の条件を保つことは別です。何を選び得るかという範囲をそのまま守る必要があります。

初期配列から一回の交換を確かめる

5要素A・B・C・D・Eについてiとjを選び、一回の交換前後を比べます。入力ごとに同じ初期配列へ戻る例です。

入力値を確かめる準備ができました。

各jを等確率で選ぶことが均等なシャッフルの条件です。

3要素なら6本の選択経路をすべて追える

最初のjは3通り、次のjは2通りです。それぞれの選択が正しい範囲で等確率なら、選択経路は6通りで、各経路の確率は1/3×1/2=1/6になります。

最初のj次のj最終的な並び
00BCA
01CBA
10CAB
11ACB
20BAC
21ABC

最初に0を選ぶ二つの経路

ABCでiが2、jが0ならCBAになります。次のiが1でjが0ならBCA、jが1ならCBAです。末尾のAは最初の段階で固定され、残りのBとCだけが入れ替わるか、そのまま残るかの違いになります。

2つの経路はどちらも1/6です。末尾がAという大きな条件には合計1/3の確率があり、その中の二つの並びへ半分ずつ分かれる形です。段階ごとの確率を掛ける意味が、小さな例で見えます。

最初に1または2を選ぶ経路

最初にjが1ならACBで、次のjが0ならCAB、jが1ならACBです。最初にjが2ならABCのままで、次のjが0ならBAC、jが1ならABCになります。全部を集めると6通りが一度ずつ現れます。

同じ並びへ二つの異なる経路が重なっていないことも、等確率の確認で重要です。経路が均等でも、複数の経路が一つの結果へ集まるなら、その結果の確率は大きくなります。この3要素の表では経路と結果が一対一で対応します。

一般の要素数でも確定範囲を分ける

N要素では、末尾の選択が1/N、その前が1/(N−1)というように範囲が縮みます。すべての選択を掛けると1/N!です。各段階で残りのどれでも選べることが、全体の並びを同じ確率へそろえる関係につながります。

この説明は、選ばれる整数が各範囲で均等であるという前提を使います。交換の手順が正しくても、交換相手の乱数が偏っていれば同じ結論にはなりません。並べ替えの手順と、その手順へ渡す乱数の性質を分けて確認します。

カードの順序を入れ替える実物のトランプ
カードの順序を入れ替える実物のトランプ · meettya / CC BY 2.0 · 写真クレジット

交換相手を毎回全範囲から選ぶと別の方式になる

よく似た動きでも、交換相手の範囲を変えると別のアルゴリズムです。各位置を一度ずつ訪れ、毎回すべての位置から相手を選ぶ単純な方式は、Fisher–Yatesと同じ等確率の性質を持つとは限りません。

3回とも3択なら選択経路は27本

3要素について3回の操作を行い、毎回0・1・2から選ぶと、選択経路は3×3×3=27通りです。もしすべての経路が同じ確率なら、6つの並びへ均等に分けるには27を6で割り切る必要があります。しかし27÷6は整数ではありません。

したがって、その条件のまま6つの並びへ同じ数の経路を配ることはできません。見た目に何度もカードが動いていても、結果の並びが等確率になるとは限らないことを、経路の本数から確かめられる例です。

回数を増やすことは同じ証明の代わりにならない

何度もランダムな交換を繰り返すと、ある条件では分布が変化していきます。しかし、回数を増やしたから元の方式がFisher–Yatesと同じになるわけではありません。必要な回数や残る偏りを調べるには、別の分析が必要です。

一回の線形な手順で全体の並びを等確率へそろえる目的と、繰り返しの交換で分布を混ぜる目的を分けます。手順の名前が似ていても、証明に使っている条件が違えば、そのまま結論を移すことはできません。

選ばない範囲を固定することにも意味がある

Fisher–Yatesでは、確定した末尾を未確定の範囲へ戻しません。これは単に処理を速くするための省略ではなく、選択と結果を一対一で追う関係に関わります。どの位置がまだ動いてよいかという情報が、手順の一部です。

iを2から1へ下げると、規則上のjの上限も2から1へ変わります。上限を常に最初の長さのままにする誤りや、iを含めない誤りは、画面の動きだけでは見つけにくいため、範囲の数値を合わせて確認することが重要です。

ランダムな比較でソートする方法とは分ける

ソートは、要素同士の順序の関係を比較して並べる処理です。比較のたびにランダムな答えを返す方法は、整合した順序の関係を前提とする通常の比較と異なります。

比較の答えが呼ぶたびに変わる

ある比較でAがBより前、次でBがAより前となれば、一つの固定した順序関係を作っていません。ソートの呼び出し方や実装によって、どの比較が何回起きるかも変わるため、等確率の並びを得る仕組みとして同じ証明を使えません。

短いコードで一見よく混ざった結果が出ても、すべての並びの確率が同じかは別の問いです。動作したこと、元と違う並びになったこと、等確率であることを順番に分けて確認します。

ソートの結果は実装の条件にも依存する

比較の順序や回数が変わると、使われるランダムな値の数も変わる場合があります。ある環境で観察した並びの頻度を、そのまま別の環境へ一般化することはできません。ソートはシャッフル用の手順として設計されたものとは役割が異なります。

確率の条件を明示したいなら、未確定の範囲から一つを選ぶというシャッフルの操作を直接書くほうが、何を数えているかを追いやすくなります。短さだけでなく、選択肢と結果の対応が説明できるかが重要です。

均等な整数を作る部分も別に調べる

0からiまでの整数へ乱数を対応させる際、元の値の個数が範囲の大きさで割り切れないと、単純な余りの計算で偏りが生じる場合があります。これは交換の手順とは別の層の問題です。

たとえば8種類の値を6種類へ余りで押し込む例と、Fisher–Yatesの選択範囲の誤りは、どちらも偏りへつながり得ますが原因が違います。どこで均等性が必要かを分けると、アルゴリズムの説明を一つの曖昧な「ランダム」でまとめずに済みます。

カードの順序を入れ替える実物のトランプ
カードの順序を入れ替える実物のトランプ · Jud McCranie / CC BY-SA 4.0 · 写真クレジット

小さな全経路の確認と、大きな標本の観察を分ける

3要素ならすべての選択経路を数えられます。大きな要素数では全列挙が急に難しくなるため、手順の条件の説明と、実行結果の観察を組み合わせて確認します。標本だけで証明を置き換えることはできません。

一度の結果は均等性の判定にならない

一回のシャッフルでABCが出たとしても、1/6の条件へ反していません。何回か同じ並びが続いても、それだけでアルゴリズムの誤りと確定することはできません。実際に何を確かめたいのかに応じて、経路の列挙や頻度の比較を使い分けます。

反対に、数回で違う並びが多く出たから正しいともいえません。小さな標本には自然なばらつきがあります。見た目の変化の多さを、公平性の点数として扱わないことが重要です。

要素の保存は確率とは別に確認できる

シャッフル前後で、要素の種類と個数が変わっていないかは、分布の均等性と別に確かめられます。Aが消えたりBが二つになったりすれば、交換の実装の誤りを疑えます。確率の分析をしなくても見つけられる条件です。

一方、要素が正しく保存されていても、並びの確率が偏っている場合はあります。保存、範囲、停止、選択の均等性という複数の条件を分けて確認すると、どの性質が確かめられたかを過大に言わずに済みます。

学習用の手動選択は乱数の品質の試験ではない

jを自分で選ぶサンプルは、一回の交換と確定範囲の動きを理解するためのものです。人が偏りなく選べたかを判定する道具ではなく、実際のゲームの乱数や製品を検査したものでもありません。

手動で0、1、自分自身の位置という選択を試すと、各分岐でどの要素が動くかを確認できます。数値の範囲と交換の結果を対応させることで、画面の演出では見えないアルゴリズムの条件を具体的に追えます。

一回の交換を初期配列で確かめる

操作できる例は、5要素A・B・C・D・Eの初期配列から一回の交換を示します。現在のiとjを入力するたびに初期配列へ戻るため、連続したシャッフル全体の履歴とは分けて読みます。

iを4、jを1にする

初期配列A・B・C・D・Eでiが4、jが1なら、位置4のEと位置1のBを交換し、A・E・C・D・Bになります。位置番号は0始まりで、5要素の右端は4です。交換した二つ以外の要素は同じ位置に残ることを確認できます。

Fisher–Yatesの連続した手順なら、この交換の後は右端の位置4を確定し、次のiを3へ下げます。一方、この短い操作例は一回の交換を初期配列に対して示すものです。次の入力へ前回の並びが引き継がれると考えず、表示された交換前の配列を毎回読みます。

jをiと同じ4にする

iが4でjも4なら、同じ位置を交換するためA・B・C・D・Eのままです。見た目が動かなくても、現在の右端の要素をそこへ残すという選択を確認できます。全体のシャッフルでは、この自分自身の位置も等確率で選ぶ範囲へ含めます。

jを1とした場合と4とした場合を比べれば、同じ初期配列の同じiでも、選んだ相手によってどの要素が末尾へ入るかが変わります。操作例のjは手動で指定するため、そこで得た頻度をランダムな選択の試験結果として扱いません。

未確定範囲の上限を変える

iを3、jを0にすると、この例の初期配列ではDとAが入れ替わり、D・B・C・A・Eになります。iが3なのにjへ4を指定するのは、未確定範囲0〜3の外から相手を選ぶ条件です。範囲の端が交換の手順に関わることを確かめます。

一回の位置交換と、毎回の結果を引き継いで最後まで実行するシャッフルは別の段階です。3要素の6経路の表は全体の選択を追う例、この操作欄は指定した一回の交換を確認する例として読み分けます。どの範囲を固定したかが分かれば、途中の数字を全体の確率と混同せずに済みます。

カードの順序を入れ替える実物のトランプ
カードの順序を入れ替える実物のトランプ · 写真クレジット

よくある質問

元の並びのままになったら失敗ですか?

いいえ。元の並びも対象とする順列の一つです。3要素の6通りを等確率にするモデルなら、元と同じ並びも1/6で得られます。

交換相手の範囲はどこまでですか?

後ろから進める形では、現在の位置iに対し0からiまでです。確定した末尾の範囲を再び交換相手へ戻しません。

自分自身との交換を省いてもよいですか?

省くと現在の要素がその場所へ残る選択肢を失います。対象とする並びの集合が変わる場合があるため、同じアルゴリズムとして扱えません。

3要素の選択経路は何本ですか?

最初が3択、次が2択なので6本です。正しい範囲から均等に選ぶ場合、各経路は1/6となり、6つの並びへ一対一で対応します。

毎回全位置から交換相手を選ぶ方式も同じですか?

別の方式です。3要素で3回とも3択にすると経路は27本となり、6つの順列へ同じ本数ずつ割り当てることができません。

ランダムな比較でソートすればよいですか?

比較の整合性やソートの実装に依存するため、Fisher–Yatesと同じ等確率の証明は使えません。選択範囲を明示した交換とは分けます。

要素が消えていなければ公平ですか?

要素の保存と並びの均等性は別の条件です。すべての要素が残っていても、特定の並びへ偏る手順はあり得ます。

手動でjを選ぶ例は乱数の試験ですか?

交換と確定範囲を追う学習用の例です。人の選び方の均等性や、個別のゲームの乱数の品質を検査するものではありません。