重み付けの抽選

解説/アルゴリズム

数値が入った配列からランダムに値を選ぶ際、中の値を重み付けとして捉え、抽選を行う。

たとえば [1, 1, 2, 3] という配列を用意した場合、要素の合計値が 7 なので、配列内の各要素が選ばれる確率は次のようになる。

$[\dfrac{1}{7}, \dfrac{1}{7}, \dfrac{2}{7}, \dfrac{3}{7}]$

コード例

export function pickWeighted(array: number[]): number {
  // 配列内の数字の合計を求める
  const total = array.reduce((a, b) => a + b, 0);
  // 配列内の数字を合計値で割った新しい配列を作る
  const probs = array.map((value) => value / total);
  // 0～1までの閾値を作る
  const threshold = Math.random();

  // 閾値を超えたときのインデックスを返す
  // もし閾値を超えない場合は確率の値を足していく
  // 例えば1回目が0.1(10%)で閾値を超えない場合、
  // 2回目が0.4(40%)の場合は、0.1 + 0.4 > 閾値の計算を行う
  let curProb = 0;
  return probs.findIndex((value) => {
    curProb += value;
    return threshold < curProb;
  });
}

import { pickWeighted } from "./random";

const array = [1, 1, 2, 3];
const result = array.slice().fill(0);
const num = 100000;

for (let i = 0; i < num; i++) {
  const i = pickWeighted(array);
  result[i]++;
}

const stats = result.map((value) => ((value / num) * 100).toFixed(2) + "%");
console.log(stats);

Array(4)
0: "14.33%"
1: "14.18%"
2: "28.39%"
3: "43.10%"

上記関数では抽選の結果が要素ではなく配列のインデックスを返す。

ソースコード

random.ts, app.ts

内部で利用しているアルゴリズム

擬似乱数