JavaScript implementation of Michael Vose's constant-time weighted random outcome generator.

AliasVose.js

// Based on Darts, Dice, and Coins: Sampling from a Discrete Distribution
// http://www.keithschwarz.com/darts-dice-coins/

export default class AliasVose {
  constructor(list) {
    // Determine relative probabilities.
    const scalar = list.length /
      list.reduce((acc, item) => { return acc + item.weight; }, 0);

    // Partition outcomes into tiny and big work queues.
    const [tinys, bigs] = reduce(list, (acc, item) => {
      const prob = item.weight * scalar;
      acc[prob < 1 ? 0 : 1].push({ prob: prob, item: item });

      return acc;
    }, [[], []]);

    this.table = [];

    while (tinys.length && bigs.length) {
      const tiny = tinys.pop();
      const big = bigs.pop();

      // Add tiny work item to table, top off with big work item.
      this.table.push({ prob: tiny.prob, item: tiny.item, alias: big.item });
      // Reduce big work item probability by top-off amount.
      big.prob += tiny.prob - 1;
      // Return big work item to tiny or big work queue.
      (big.prob < 1 ? tinys : bigs).push(big);
    }

    // Add all remaining work items to table.
    while (bigs.length || tinys.length) {
      this.table.push({ prob: 1, item: (bigs.pop() || tinys.pop()).item });
    }
  }

  rand() {
    // Choose a table entry, then choose its tiny or top-off item.
    const bucket = this.table[Math.floor(Math.random() * this.table.length)];
    return Math.random() < bucket.prob ? bucket.item : bucket.alias;
  }
}

// // Usage:
// // Create an outcome producer by initializing with outcomes and weights.
// const vose = new AliasVose([
//   { weight: 20, label: 'Aloof' },
//   { weight: 32, label: 'Bereft' },
//   { weight: 16, label: 'Complicit' },
//   { weight: 40, label: 'Dependent' },
//   { weight: 16, label: 'Egregious' },
//   { weight: 16, label: 'Fickle' },
//   { weight: 20, label: 'Garrulous' }
// ]);
//
// // Generate outcomes, and tally how many times each outcome occurs.
// const results = {};
// for (var i = 50000; i > 0; i--) {
//   const out = vose.rand();
//   results[out.label] = (results[out.label] || 0) + 1;
// }
//
// Take a look at the results.
// {
//   "Aloof": 6142,
//   "Bereft": 9951,
//   "Complicit": 5147,
//   "Dependent": 12510,
//   "Egregious": 4961,
//   "Fickle": 5003,
//   "Garrulous": 6286
// }