ランダムに配列をシャッフルする「Fisher-Yates shuffleアルゴリズム」を理解した

2020/05/10 17:57 追記：shuffleがshufflになっていたのを訂正

シャッフルアルゴリズムとしてはかなり有名な部類だそう。Fisher-Yatesってなんて読むんだろう。

設定、目標、制約等

長さ $n$ の順列 $p$ をランダムに並び変えたい。効率の良い方法を見つける。
ただし乱数生成器の偏りとかは考えてもしょうがないので無視する。
以降、rand(a, b)で $a$ 以上 $b$ 以下の整数値をランダムに取得できると仮定する。0-indexedとして説明する。

まずは考えてみる

rand(0, n-1)で整数値 $i, j$ を2つ取得してswap(p[i], p[j])する。この操作を十分な回数行うとシャッフルされるように思う。
でも少し考えてみると、例えば $n$ 回数値をswapしたとき、2回以上swapされる数値や、逆に1回もswapされない数値が出てくることがわかる。試行回数を無限回に増やせば偏りは無くなるが、実行時間も無限にかかることになるため現実的ではない。かといって、有限回試行した程度では偏りが無くなったとは言えない。

ところで、長さ $n$ の順列は $N!$ 通り存在する。
順列を作る作業は、「最初の要素は $0$ から $n-1$ までの $n$ 個の中から一つを選び、次の要素は $0$ から $n-1$ のうち先ほど選んだ一つを除いた $n-1$ 個の中から一つを選び、…と繰り返していく」作業と言える。そしてこの作業の各ステップは互いに独立なので、 $n \times (n-1) \times \dots \times 2 \times 1 = n!$ となる。この、「 $1$ 回目は $n$ 個の中から選び、 $2$ 回目は $n-1$ 個の中から選び、…」という操作のイメージをだいたいそのまま適用するのが今回紹介するFisher-Yates shuffleアルゴリズムだ。

Fisher-Yates shuffleアルゴリズムの手順

長さ $n$ の配列に対して以下の操作を実行する。

変数 $i$ に $n-1$ を代入して、以下の $2$ ~ $4$ の操作を $n$ 回繰り返す。
変数 $j$ にrand(0, i)を代入する。
swap(p[i], p[j])する。
$i$ の値を $1$ 減らす。

操作が終了した時点で、もとの順列の並びは完全にシャッフルされている。

アルゴリズムを理解する

上記の説明中の変数で、 $i$ は確定させていない要素のうち一番末尾の要素を表す。また、 $j$ は確定させていない要素のうちの一つをランダムに選ぶ。
配列を確定していない部分(前半)と既に確定している部分(後半)に分ける。確定していない部分のうち一番最後の要素を、まだ選ばれていない要素の中からどれにするか選ぶというイメージ。選ばれた要素は末尾に固定され、その後選ばれることはない。つまり、同じ要素が $2$ 回以上選択されることは無いということである。 $n$ 回の操作が終了した時点で、 $n!$ 通りの要素の並び方のうちどれかになる(先ほどの説明通り)。計算量は $O(n)$ となる。
実は配列の要素を比較したりしていないので、順列に限らず、どの $2$ 要素も異なるような配列ならば適用可能である。

C++での実装

アルゴリズムが単純なので、実装も数行程度とそこまで重くない。
C++での乱数生成はstd::mt19973を使うとよい。さらにある範囲から乱数を得たいときはstd::uniform_int_distributionを使うと偏り無く数値を得られる。

#include <iostream>
#include <vector>
#include <random>

std::mt19937 mt{std::random_device{}()};
void FisherYates(std::vector<int>& p){
    int n = p.size();
    for(int i = n-1; i >= 0; i --){
        std::uniform_int_distribution<int> dist(0, i);
        int j = dist(mt);
        std::swap(p[i], p[j]);
    }
}

// 以下、動作確認用コード
int main(){
    std::vector<int> p;
    int n = 10;
    for(int i = 0; i < n; i ++){
        p.push_back(i);
    }

    FisherYates(p);

    for (int i = 0; i < n; i ++){
        std::cout << p[i] << std::endl;
    }
    return 0;
}

ちなみに

「ふぃっしゃーいぇーつ」と読むらしい。勉強になりました。

参考文献

Fisher–Yates shuffle - Wikipedia
Wikipediaです。こら！Wikipediaを参考文献にしてはいけません！

ランダムシャッフル | Programming Place Plus アルゴリズムとデータ構造編【その他のアルゴリズム】第２章
単純なswapによるシャッフルが偏ってしまう説明があり、わかりやすいです。

C++の乱数ライブラリが使いにくい話 - Qiita
C++で乱数生成するための方法が色々まとめてあります。

3匹の猫

みみねこの競プロ精進メモ