smoothed-random-selections.js

'use strict';

// type Item = {
//   // Default: 1
//   preferenceWeight: number;
//
//   // Should be initialized with preferenceWeight
//   weight: number;
// };
//
// type Items = Item[];

function selectByWeight(items, rand = Math.random()) {
  const weightSum = items
    .map(item => item.weight)
    .reduce((w1, w2) => w1 + w2)
  ;
  
  let randRemaining = rand * weightSum;
  
  for (const item of items) {
    randRemaining -= item.weight;
    
    if (randRemaining < 0) {
      return item;
    }
  }
  
  throw new Error('Item should always be picked in algorithm above.');
}

// inflationPerRound:
//
// This parameter determines how much the probability of picking an item with .preferenceWeight === 1 should be multiplied by (approximately)
// if a full round of selections are made except for that item. A full round is when every item is picked with a frequency equal to its
// .preferenceWeight. Fractional .preferenceWeight values are allowed, e.g. if .preferenceWeight is P / Q, then Q full rounds would include P
// selections of that item.
//
// The reason this is approximate is because the probabilities must always add up to 1, so if an item is never selected, it can only asymptotically
// approach a 100% probability of selection, rather than accumulating without bound.
//
// For example, with inflationPerRound === 5 and the following items:
// [ { name: 'Orange', weight: 1, preferenceWeight: 1 },
//   { name: 'Apple',  weight: 2, preferenceWeight: 2 },
//   { name: 'Pear',   weight: 3, preferenceWeight: 3 } ]
//
// Then an example of a full round could be:
// Orange, Apple, Apple, Pear, Pear, Pear
//
// After this occurs, the items would return to their starting weights.
//
// However, if instead Orange was not selected:
// Apple, Apple, Pear, Pear, Pear
//
// Then the items would now be:
// [ { name: 'Orange', weight: 5, preferenceWeight: 1 },
//   { name: 'Apple',  weight: 2, preferenceWeight: 2 },
//   { name: 'Pear',   weight: 3, preferenceWeight: 3 } ]
//
// And the chance of selecting Orange would increase from its long term average of 1/6 to 5/10.

function acceptSelection(items, acceptedItem, inflationPerRound) {
  const preferenceWeightSum = items
    .map(item => item.preferenceWeight)
    .reduce((w1, w2) => w1 + w2)
  ;
  
  const logInflationPerRound = Math.log(inflationPerRound);
  
  for (const item of items) {
    if (item === acceptedItem) {
      item.weight *= Math.exp(-logInflationPerRound);
    } else {
      item.weight *= Math.exp(logInflationPerRound * item.preferenceWeight / (preferenceWeightSum - item.preferenceWeight));
    }
  }
}

function randExample() {
  const items = [
    { name: 'Orange', weight: 1, preferenceWeight: 1 },
    { name: 'Apple',  weight: 2, preferenceWeight: 2 },
    { name: 'Pear',   weight: 3, preferenceWeight: 3 },
  ];
  
  const inflationPerRound = 5;
  
  for (let i = 0; i !== 20; i++) {
    const item = selectByWeight(items);
    acceptSelection(items, item, inflationPerRound);
    console.log(`Selected: ${item.name.padEnd(8)}, new weights: ${items.map(it => it.weight.toFixed(2).padStart(6)).join(', ')}`);
  }
}

function roundExample() {
  const items = [
    { name: 'Orange', weight: 1, preferenceWeight: 1 },
    { name: 'Apple',  weight: 2, preferenceWeight: 2 },
    { name: 'Pear',   weight: 3, preferenceWeight: 3 }
  ];
  
  const inflationPerRound = 5;
  
  for (const item of items) {
    if (item.name === 'Orange') {
      continue;
    }
    
    for (let i = 0; i !== item.preferenceWeight; i++) {
      acceptSelection(items, item, inflationPerRound);
      console.log(`Selected: ${item.name.padEnd(8)}, new weights: ${items.map(it => it.weight.toFixed(2).padStart(6)).join(', ')}`);
    }
  }
  
  acceptSelection(items, items[0], inflationPerRound);
  console.log(`Selected: ${items[0].name.padEnd(8)}, new weights: ${items.map(it => it.weight.toFixed(2).padStart(6)).join(', ')}`);
}