【JavaScript】重み付けされた値をランダムで取得する

ガチャやゲームをつくるときや、マルコフ連鎖で文章を生成するときなど、重み付けされた値をランダムで取得したいときがある。
ということで、JavaScriptで実装してみた。

重み付けされたリストから値を取得する

// 値と重みのリスト[[val, weight], [val, weight], ...]
var ProbabilisticChoice = function (valuesAndProbabilities) {
    var lists = valuesAndProbabilities;
    var totalWeight = (function () {
        var sum = 0;
        lists.forEach(function (list) {
            sum += list[1]; // weight
        });
        return sum;
    })();

    return {
      pick: function () {
          // 0〜totalWeight の範囲でランダムな値を取得
          var r = Math.random() * totalWeight;
          var s = 0.0;

          for (list in lists) {
              s += lists[list][1];
              if (r < s) { return lists[list][0]; }
          }
      }
    };
};

// 重み付けリスト
bloodLists = ProbabilisticChoice([['A', 4], ['B', 2], ['O', 3], ['AB', 1]]);
// 確認用オブジェクト
types = { 'A': 0, 'B': 0, 'O':0, 'AB': 0};

// 10万回試行する
for (var i = 0; i < 100000; i++) {
    // 値の取得
    var blood = bloodLists.pick();
    types[blood] += 1;
}

// 結果の出力
console.log(JSON.stringify(types, '', ' '));

重み付けされたサンプル（血液型）は[('A', 4), ('B', 2), ('O', 3), ('AB', 1)]の4つ。
※ 重みは合計で10にならなくても良い

このサンプルで10万回×3回試行した結果が以下のとおり。

1回目: {A: 39885, B: 19953, O: 30078, AB: 10084}
2回目: {A: 40038, B: 20033, O: 30034, AB: 9895}
3回目: {A: 39835, B: 19971, O: 30202, AB: 9992}

だいたいA型が4割、B型が2割、O型が3割、AB型が1割と重みのとおりに分布した。


処理の詳細は以下のとおり。

1. 重みの合計を算出する → totalWeight
2. 0 〜 totalWeightの範囲でランダムな値を取得する → r
3. 重み付けされたリストのどの場所にあたるか計算する

パッと見、何をしているのかわかりにくいかもしれないが、実際に手で計算すればすぐ理解できると思う。

---

追記: 2016/12/09 14:30
より良さげな書き方を思いついた。

// 値と重みのObject配列[{item: value, weight}, ...]
const ProbabilisticChoice = (list) => {
  const totalWeight = list.reduce((p, c) => {
    return { weight: p.weight + c.weight }
  }).weight
  
  return {
    pick () {
      const r = Math.random() * totalWeight;
      let s = 0.0;
      for (const l of list) {
        s += l.weight
        if (r < s) { return l.item }
      }
    }
  }
}
 
// 重み付けリスト
bloodLists = ProbabilisticChoice([
 { item: 'A' , weight: 4 },
 { item: 'B' , weight: 2 },
 { item: 'O' , weight: 3 },
 { item: 'AB', weight: 1 }
])

// 確認用オブジェクト
types = { 'A': 0, 'B': 0, 'O':0, 'AB': 0}
 
// 10万回試行する
for (var i = 0; i < 100000; i++) {
    // 値の取得
    var blood = bloodLists.pick()
    types[blood] += 1
}
 
// 結果の出力
console.log(JSON.stringify(types, '', ' '))

---

以上

written by @bc_rikko