How to choose a weighted random array element in Javascript?

Question

Both answers above rely on methods that will get slow quickly, especially the accepted one.

This is a function which just takes two same-length lists, items and weights, and returns a random item from items according to their corresponding likelihoods of being chosen in weights. The weights array should be of nonnegative numbers, but it doesn’t need to sum to a particular value, and it can handle non-integer weights.

function weighted_random(items, weights) {
    var i;

    for (i = 1; i < weights.length; i++)
        weights[i] += weights[i - 1];
    
    var random = Math.random() * weights[weights.length - 1];
    
    for (i = 0; i < weights.length; i++)
        if (weights[i] > random)
            break;
    
    return items[i];
}

I replaced my older ES6 solution with this one as of December 2020, as ES6 isn’t supported in older browsers, and I personally think this one is more readable.

If you’d rather use objects with the properties item and weight:

function weighted_random(options) {
    var i;

    var weights = [options[0].weight];

    for (i = 1; i < options.length; i++)
        weights[i] = options[i].weight + weights[i - 1];
    
    var random = Math.random() * weights[weights.length - 1];
    
    for (i = 0; i < weights.length; i++)
        if (weights[i] > random)
            break;
    
    return options[i].item;
}

Explanation:

I’ve made this diagram that shows how this works:

Diagram showing items' weights and how they add up and interact with the random numbers. Without this diagram this explanation isn't very helpful, so feel free to ask me any questions about it in a comment if it won't render for you.

This diagram shows what happens when an input with the weights [5, 2, 8, 3] is given. By taking partial sums of the weights, you just need to find the first one that’s as large as a random number, and that’s the randomly chosen item.

If a random number is chosen right on the border of two weights, like with 7 and 15 in the diagram, we go with the longer one. This is because 0 can be chosen by Math.random but 1 can’t, so we get a fair distribution. If we went with the shorter one, A could be chosen 6 out of 18 times (0, 1, 2, 3, 4), giving it a higher weight than it should have.

Leave a Comment Cancel reply