How to generate a random weighted distribution of elements

Question

I would like to return an array which has a set of unique elements randomly distributed according to custom frequency. My real world use-case is the repetition of carousel images based on a qualitative weighting of how popular those images are.

E.g. suppose I have 5 elements with weights:

A, 20% B, 50% C, 80% D, 10%

I would like to write a function that, given a length, tries to approximate a sequence such that C will appear eight times more often than D; D will appear 5 times less often than B; A will appear three times less often than C.

Answer 1

C will appear eight times more often than D; D will appear 5 times less often than B; A will appear three times less often than C.

You can do that with a weighted array of your elements:

var elems = ["A", "B", "C", "D"];
var weights = [2, 5, 8, 1]; // weight of each element above
var totalWeight = weights.reduce(add, 0); // get total weight (in this case, 16)

function add(a, b) { return a + b; } // helper function

var weighedElems = [];
var currentElem = 0;
while (currentElem < elems.length) {
  for (i = 0; i < weights[currentElem]; i++)
    weighedElems[weighedElems.length] = elems[currentElem];
  currentElem++;
}

console.log(weighedElems);

This will produce an array like

["A", "A", "B", "B", "B", "B", "B", "C", "C", "C", "C", "C", "C", "C", "C", "D"]

so you can choose randomly from that like so

var rnd = Math.floor(Math.random() * totalWeight);
console.log(weighedElems[rnd]);

Resources:

• Generate A Weighted Random Number
• Weighted random number generation in Javascript
• Algorithm for generating weighed random numbers

Answer 2

Let's say you take your distribution numbers as an array of objects, like this:

var items = [
    {item: "A", weight: 20}, 
    {item: "B", weight: 50}, 
    {item: "C", weight: 80},
    {item: "D", weight: 10}
];

This removes any assumption that your weights add up to 100% - they might be click-counts, or votes, or any other value you like. Then you can do this:

function weightedSelect(items) {
    // Get the total, and make the weights cummulative
    var total = items.reduce(function(sum, item){
        item.weight = item.weight + sum;
        return item.weight;
    },0);

    var r = Math.random() * total;

    // Can't use .forEach() here because we want early termination
    for (var i = 0; i < items.length; i++) {
         if (r < items[i].weight)
             return items[i].item;
    }
}

I'm not sure how this compares to the other implementations for efficiency, but it's concise.