世界最速の配列シャッフルアルゴリズム、Fisher-Yatesアルゴリズム

調べ物をしていたら、Fisher–Yatesアルゴリズムを見つけました。考え方がとてもシンプルでよかったので紹介します。

Fisher–Yatesアルゴリズムって何?

Fisher–Yatesアルゴリズムとは、シャッフルアルゴリズムのひとつで 最速のシャッフルアルゴリズム です。

Fisher–Yatesでは、 配列からランダムに要素を抽出して並べていきます。

for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]]; // i と j を入れ替え
}

このアルゴリズムは一見すると適当に並べているように見えますが、きちんとランダムに並べ替えられます。

このアルゴリズムのポイントは、 入れ替えられた要素が2回入れ替わることがない点です。

入れ替えた要素が再び移動することはない

1. Fisher-yatesはループの現在地点iと、iより前にある要素からランダムに選んで入れ替える
2. iは、はじめは配列の末尾を指していて、1回入れ替えるごとに1つずつ減っていく

つまり、一度選ばれた要素は i の位置に回されてi はひとつ減るので、入れ替えられた要素が再び選ばれることはありません 。見方を変えると、配列を「入れ替えていない要素」と「入れ替え済みの要素」に分け、iは入れ替えていない要素の末尾を指していると考えられます。

入れ替えの途中経過(オレンジ部分が入れ替え済みの要素)

このように、白いエリアから選んだものをオレンジエリアに入れていっているのでランダムに並べ替えられています。

抜き出して並べるアルゴリズムと比較する

実はこのアルゴリズムは、配列から一個ずつ要素をランダムに選んで空の配列に移していくのと本質的に変わりません。これを1つの配列内で行っているだけです。i より前部分が与えられた配列で、iから後ろが新しい配列と考えると分かると思います。

ちなみに一つずつ抽出して別の新しい配列に入れていくコードはこのようになります。見るとわかりますが、shuffle2()はほとんどshuffle()と同じです。

const shuffle2 = arr => {
    // arrに破壊的変更を加える
    const result = [];
    for(let len = arr.length; len > 0; len--) {
        const i = 0 | Math.random() * len;
        result.push(arr.splice(i, 1));
    }
    return result;
};
// arr = shuffle2(arr);

さて、ここまでの解説で理解していただけたかと思いますが、Fisher-Yatesは 計算量が配列の長さ分 しかありません。ランダウ記法を用いると、配列の長さをnとしてO(n)です。O(n)を超えるにはO(log n) か O(1) にしなければなりませんが、少なくともn回の入れ替えを実施しなければならないので、不可能です。これが最速と呼ばれる所以です。

終わりに

Fisher-Yatesアルゴリズムはきちんと論理立てられて、簡潔化、最適化されています。 しかし、論理的で簡潔であるがゆえに直感的でなくわかりづらいです。この解説がみなさんの理解の助けになったらうれしいです。