Fisher-Yates Shuffle

C++

てきとうに抜粋して書く。

以下のシャッフルアルゴリズムは間違っていて、

def incorrect_shuffle(items):
    for i in range(len(items)):
        randomIndex = random.randint(0, len(items)-1)
        temp = items[randomIndex]
        items[randomIndex] = items[i]
        items[i] = temp
    return items

これには、以下の3つの問題がある：

  1. 偏る
  2. 偏る
  3. 偏る

実は1つだったけど、これは大きな問題だ。

Fisher-Yates Shuffle (Knuth Shuffleとも呼ばれる)の実装は、以下のようになる：

def fisher_yates_shuffle(items):
    for i in range(len(items)):
        randomIndex = random.randint(i, len(items)-1)
        temp = items[randomIndex]
        items[randomIndex] = items[i]
        items[i] = temp
    return items

違いは、以下の1行。

従来のアルゴリズム：

randomIndex = random.randint(0, len(items)-1)

Fisher-Yatesのアルゴリズム：

randomIndex = random.randint(i, len(items)-1)

乱数範囲の開始が0がiになっただけだけど、統計をとると偏りがなくなったことがわかる：

ちなみに、C++標準ライブラリに含まれるstd::shuffle()の実装を調べたところ、GCC 4.9 (libstdc++)、Clang 3.4 (libc++)、MSVC2013のいずれも、Fisher-Yatesを使っていた。([i, size)ではなく[0, i)のバージョン)

参照

変更履歴

  • 2014/08/12 15:14 MSVCは従来のアルゴリズムではなくFisher-Yatesを使っていたので、訂正
  • 2014/08/12 15:18 libstdc++とlibc++もFisher-Yatesだったので訂正