Fisher-Yates法

配列をシャッフルする際に用いられるアルゴリズムとして,Fisher-Yates法は非常に有名なのではないでしょうか.

Fisher-Yates法によるシャッフルアルゴリズムは,以下のようなコードになります.

def shuffle(array):
    for i in range(len(array)):
        r = random.randint(i, len(array) - 1)
        tmp = array[i]
        array[i] = array[r]
        array[r] = tmp
    return array

ときたま,Fisher-Yates法のアルゴリズムを以下のように実装しているコードを見かけます.

def shuffle(array):
    for i in range(len(array)):
        r = random.randint(0, len(array) - 1)
        tmp = array[i]
        array[i] = array[r]
        array[r] = tmp
    return array

しかし,このコードは厳密なシャッフルを行えないため,間違いがあるコードです.

今回は,なぜこのコードが間違っているのか,ということを,配列の長さがの場合を例にして証明してみたいと思います.

証明すること

まず,配列の長さとします.

シャッフルコードが正しいアルゴリズムになっているなら,配列の番目の要素がシャッフル実行後に番目となっている確率は,偏りなく均等になっているはずです.

つまり,配列の番目の要素が,番目となっている確率をとすると,となっているはずです.

しかし,間違ったコードの書き方では,この確率に偏りが生じてしまいます.

以降では,間違ったコードを実行した場合の確率を計算し,実際に偏りが生じてしまっていることを示します.

の導出

を計算するために,コードのループ部分を回実行した後に,番目の要素が番目となっている確率をとし,この確率を順々に計算していきます.

の漸化式

まず,順々に計算を行っていくために,の漸化式を導出します.

は,を用いると,以下のように表すことができます.

上の式では,の場合と,の場合で場合分けをしています.

これは,番目に入れ替える対象がまさに番目であるというケースと,それ以外とで分けて考えている,ということです.

の場合,それまでに配列のどのインデックスにいようとも,入れ替えられる対象として選ばれた場合,回目のループ実行後に番目の要素となることができます.

したがって,の場合,入れ替えられる対象として選ばれる確率になります.

一方での場合,回目のループ実行前に既に番目にいるか,回目のループ実行前に番目にいる,という2つの条件のいずれかを満たしていなければなりません.

前者の条件を満たしている場合,番目の要素が入れ替えられる対象として選ばれることがなければ,回目のループ実行後に番目の要素となることができます.

前者の条件を満たす確率はであり,番目の要素が入れ替えられる対象として選ばれる確率はなので,前者の条件を満たし回目のループ実行後に番目の要素となる確率はとなります.

後者の条件を満たしている場合,番目の要素が入れ替えられる対象として選ばれれば,回目のループ実行後に番目の要素となることができます.

後者の条件を満たす確率はであり,番目の要素が入れ替えられる対象として選ばれる確率はなので,後者の条件を満たし回目のループ実行後に番目の要素となる確率はとなります.

結局,の場合,これら2つの確率を足し合わせて,と計算されます.

漸化式が導出できたので,あとはから順々に計算を行っていきましょう.

の場合の計算

(1) の時
(2) の時

の場合の計算

(1) の時
(2) の時
(3) の時

の場合の計算

(1) の時
(2) の時
(3) の時
(4) の時

の場合におけるの導出

までの確率を計算することができたので,これを使ってとした場合の確率の式を計算してみましょう.

主に3.4節の式にを代入すればよいのですが,の場合はになることがありえないため,式をもうすこし簡潔に書けるようになります.

(1) の時
(2) の時
(3) の時

に関しては確率に偏りがないことが分かりますが,に関しては確率に偏りが生じていることが分かります.

これでは配列の要素の初期順によって結果に偏りが生じるため,偏りなく均等にシャッフルを行いたいという意図に反してしまっています.

配列のシャッフルコードを書く場合には,確率に偏りが生じていないか実験してみてデバッグをしてみるのが良いでしょう.

最後に

本当はが任意の値の場合の確率の式を導出したかったのですが,イマイチ規則性が分からなかったのでの計算をしている途中で断念してしまいました.

そのうち任意のに対する式を導出するつもりです,そのうち...