逃げ出す鯨

クーポンコレクター問題をjsで実装する

クーポンコレクター問題とは？

クーポンコレクター問題とは簡単に言うと

という、期待値を求める問題です

もう少し具体的に言うと、サイコロを振って全部の目が出るまで平均何回かかるか、ということ

いわゆるガチャとか、ブロマイド入りCDとか、そういうものと考えてください

余談

昔ゲーム系のアプリを担当した際に、モンスターの発生がランダムで実装されており、

重み付きの抽選ではあるものの、全種類現れることを担保するテストがありました

僕が参画する前からそのテストはありましたが、極稀に失敗することもあり、

いったい何回の試行が必要なのか不明という問題がありました

そこで見つけたのが、このクーポンコレクター問題というわけです

計算方法

僕自身が数学に精通しているわけではないので、リンク先の解説を見てください

クーポンコレクター問題 -ニコニコ大百科

結論としては下記です

E(N) = n×(1/1 + 1/2 + ... + 1/(n-1) + 1/n)

つまり、n種類について全種類揃うまで揃っていないものが当たる確率を足していけばいいということです

展開すると (n * 1/1) + (n * 1/2) + ... (n * 1/(n - 1)) + (n * 1/n) になります

これなら簡単にループで回せばよさそうですね

単純な実装

ループを回して足していくパターン

function coupon(n)  {
    let avg = 0;
    for(let i = 1; i <= n; i++) {
        avg += n * (1 / i);
    }
    return avg;
}

単純に avg に n * (1 / i) を足していくだけ

少し冗長だが、可読性は文句なしですね

大百科の例によりサイコロ(6)を実行するときちんと14.7となります

[改良] Array.reduce を使う

これは今の値と配列の中身を順に渡してくれる関数です

コールバックに初期値を指定しない場合、初回呼び出しで1つ目の要素がaに入り、bには次の値が入ります

まず [...Array(n + 1).keys()] で [0, 1, 2, 3, 4, 5, 6] をつくります

​ この ... はスプレッド構文、Array.keysはイテレータを返すので展開する

n + 1 としているのは、Arrayの中身にnがほしいからです

詳しくは Array.prototype.reduce() の reduce() はどう動くか を参考のこと

そうすると、初期値a = 0に対して、bに1が入ってくるので、n / 1, n / 2... と計算したものを足していきます

function coupon(n)  {
    return [...Array(n + 1).keys()].reduce((a,b) => a += n / b);
}

可読性は度外視で、これでだいぶ短くできました

どちらを使うかはチームメンバーのスキルによると思います

こちらもどうぞ BearBlogの書き方

↓ よかったら下の[Toast this post]のクリックをおねがいします