シャッフルした結果が偏ると相談を受けたときに確認すること

はじめに

ソフトウェアエンジニア職ではない同僚が作って運用してくれている GAS スクリプトがある。これは、スプレッドシートに事前に列挙しておいた社内メンバーのリストから、4 人 1 グループを複数作るという代物だ。それぞれのグループにはリーダーを立てる仕組みになっているのだが、このリーダーが連続して特定の人に偏ることがあった。実はこのリーダーは重い責任を負うので、あまりなりたくないのだ。

ちょっと見てほしいと言われて、覗いてみたソースコードは簡略化すると次のような実装になっていた。

// これは本当はスプレッドシートから取ってくる
var members = ["A","B","C","D","E","F","G","H"]

// ここでメンバーをシャッフルする
for (var i in members) {
    var random = Math.floor(Math.random() * members.length);
    var tmp = members[i];
    members[i] = members[random];
    members[random] = tmp;
}

// 4 人に 1 人がリーダーに選出されて、それ以外が同じグループに入るロジックになってる
for (var i in members) {
    var value = members[i];
    if (i % 4 == 0) {
      console.log("leader:" + value)
    } else {
      console.log("not leader:" + value)
    }
}

JavaScript には Ruby のような、配列をシャッフルするビルトイン関数がないのかという感想を抱きつつ、計算量の最適化余地はありそうだがよくありそうな実装だしプロダクション運用しているわけでもなく、疑い出すと Math.random() や GAS という実行基盤まで疑わしく見えてきたので、エディタをそっと閉じてしばらく放置することにした。

出現頻度を可視化する

それから数カ月後、正規乱数の生成アルゴリズムを調べていて不意に乱数周りへの関心が高まってきたので、少し真面目に向き合うことにした。まずは上記のシャッフルアルゴリズムに実際偏りがあるのかを調べた。

// 試行回数をセットする
let count = 100000
// 配列の要素数をセットする
let n = 3
let members_counter = {}
let leaders = {}

for (let k = 0; k < count; k++) {
    let members = []
    for (let m = 1; m < n+1; m++) {
        members.push(m)
    }

    for (var i in members) {
        var random = Math.floor(Math.random() * members.length);
        var tmp = members[i];
        members[i] = members[random];
        members[random] = tmp;
    }

    if (members_counter[members.join('')]) {
        members_counter[members.join('')]++
    } else {
        members_counter[members.join('')] = 1
    }

    for (var i in members) {
        var value = members[i];
        if (i % 4 == 0) {
            if (leaders[value]) {
                leaders[value]++
            } else {
                leaders[value] = 1
            }
        }
    }
}

// 結果を確認する
for (let i in leaders) {
    console.log(i + "," + leaders[i]);
}
for (let i in members_counter) {
    console.log(i + "," + members_counter[i]);
}

メンバーが [1,2,3] と入っているときの配列シャッフルとリーダー選出を 100_000 回施行したときの結果は次の通り。リーダーは 2 > 1 > 3 の順に多く出ている。シャッフル後のメンバーも 132, 213, 231 が他 3 つよりも多く出ている。シャッフル後のメンバーの偏りがそのままリーダー選出の偏りになっていることもわかる。

どうやら上のシャッフルアルゴリズムには計算量の最適化以前に、偏りが出るという根本的な問題があることがわかった。

正しいシャッフル

配列をシャッフルするアルゴリズムのデファクトスタンダードは Fisher–Yates shuffle です。これはすべての順列の組み合わせ（Permutation）について、出現頻度の偏り（バイアス）が発生しません。実装も数行で、バイアスのある実装との差分は 2 行です。

+ for (var i = members.length - 1; i > 0; i--) {
- for (var i in members) {
+    var random = Math.floor(Math.random() * (i+1));
-    var random = Math.floor(Math.random() * members.length);
    var tmp = members[i];
    members[i] = members[random];
    members[random] = tmp;
}

一見複雑に見えますが、やろうとしているのは、大きな袋に "A", "B", "C" など文字が書かれた紙が入っていて、そこから一つずつ取り出すというロジックです。算数でいう、3! = 3 * 2 * 1 = 6 というロジックが表現されてます。元々の実装との違いは、袋から取り出した数字を袋に戻さずに確定事項としてよけておく部分だけです。同じ配列の中で、袋の中と袋の外を表現しているのが少しわかりにくい要因かもしれません。別に新しい配列を用意してそこに push して同時に members からは random 番目の要素を削除するという実装でもやっていることはそう大差ないですが、それに比べるとこちらの方がスマートですね。

この実装の場合に同じ実験を行うと、次の通り、偏りは全く見られなくなりました。

なぜ偏りが生まれるのか

配列のシャッフルとは何かというと、要素順の全組み合わせについてそれぞれが均等な確率で出現するように実装することです。つまり、[1,2,3] という配列でいうと、この順列の全組み合わせは 123, 132, 213, 231, 321, 312 の 6 通りあり、それぞれが 1/6 で出現するように実装するということです。偏りが生まれる実装では、例えばこのとき 132 が他よりも 1 回多く出てしまって 1/6 よりも多い確率で出現したりします。

上記のバイアスのある実装は Wikipedia でナイーブな実装と紹介されているので以下この名前を使っていきます。

よくよく考えると、ナイーブな実装には Fisher–Yates の背景にある袋から一つずつ取り出して 3! を行うといったロジックもないので均一性の根拠がどこにあるのか不明、という理屈で納得しかけましたが、ナイーブな実装に [1,2,3] という配列を渡したときの総当りを列挙してくれている記述を見つけたので、もう少し丁寧に深ぼります。

123
 +- 123          - swap 1 and 1 (these are positions,
 |   +- 213      - swap 2 and 1  not numbers)
 |   |   +- 312  - swap 3 and 1
 |   |   +- 231  - swap 3 and 2
 |   |   +- 213  - swap 3 and 3
 |   +- 123      - swap 2 and 2
 |   |   +- 321  - swap 3 and 1
 |   |   +- 132  - swap 3 and 2
 |   |   +- 123  - swap 3 and 3
 |   +- 132      - swap 2 and 3
 |       +- 231  - swap 3 and 1
 |       +- 123  - swap 3 and 2
 |       +- 132  - swap 3 and 3
 +- 213          - swap 1 and 2
 |   +- 123      - swap 2 and 1
 |   |   +- 321  - swap 3 and 1
 |   |   +- 132  - swap 3 and 2
 |   |   +- 123  - swap 3 and 3
 |   +- 213      - swap 2 and 2
 |   |   +- 312  - swap 3 and 1
 |   |   +- 231  - swap 3 and 2
 |   |   +- 213  - swap 3 and 3
 |   +- 231      - swap 2 and 3
 |       +- 132  - swap 3 and 1
 |       +- 213  - swap 3 and 2
 |       +- 231  - swap 3 and 3
 +- 321          - swap 1 and 3
     +- 231      - swap 2 and 1
     |   +- 132  - swap 3 and 1
     |   +- 213  - swap 3 and 2
     |   +- 231  - swap 3 and 3
     +- 321      - swap 2 and 2
     |   +- 123  - swap 3 and 1
     |   +- 312  - swap 3 and 2
     |   +- 321  - swap 3 and 3
     +- 312      - swap 2 and 3
         +- 213  - swap 3 and 1
         +- 321  - swap 3 and 2
         +- 312  - swap 3 and 3

この総当りの結果、それぞれの順列の組み合わせの出現頻度は次のようになります。

123 - 4 times
132 - 5 times
213 - 5 times
231 - 5 times
312 - 4 times
321 - 4 times
=============
     27 times total

つまり、ナイーブな実装では 3 つの要素からなる配列を渡すと、 27 通りの順列のうち一つの並びを出力しています。そしてその 27 通りの内訳は結局 6 つのユニークな順列のどこかに集約されるので、123 が 4/27、132 が 5/27、213 が 5/27、231 が 5/27、312 が 4/27、321 が 4/27 の確率で出現します。これはそれぞれが 1/6 で出現するという均一さの期待値からズレがあるので偏ってます。

別の言い方をすると、ナイーブな実装は、一度袋から数字を取り出したらまた元に戻して引き直す形で順列を計算するロジックが根底にあります。算数を思い出してもらうと n^n = 3^3 = 27 通りの重複込みの順列です。これを順列の重複がない 6 通りの組み合わせで表現しようとどう頑張っても割り切れない以上、27%6 = 3 通りが余りとしてバイアスの形で現れます。

まとめ

シャッフル関数を自前で実装するときは Fisher–Yates shuffle を使えば問題ありません。数行で実装できます。一度理解すれば、怖くありません。むしろナイーブな実装のほうが理解しづらくて怖いです。ビルトイン関数が提供されていない JavaScript などを使う実行環境だと、プロダクションでは lodash.shuffle などを使うことも多いですが、GAS だと自前で実装しがちです。Fisher–Yates 以外の一見わかりやすい実装は、計算量の話以前にちゃんとシャッフルできていない可能性があるので気をつけたほうが良いです。時間がなければなおさら避けたほうが良いでしょう。

余談

これを期に社内のプロダクション（ミニゲーム）でシャッフル自前実装をしている箇所を検索したところ、ちゃんと Fisher–Yates で実装されてました😊