How to choose a weighted random array element in Javascript?

Question

For example: There are four items in an array. I want to get one randomly, like this:

array items = [
    "bike"    //40% chance to select
    "car"     //30% chance to select
    "boat"    //15% chance to select
    "train"   //10% chance to select
    "plane"   //5%  chance to select
]

Answer 1

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

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:

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.

Answer 2

Some es6 approach, with wildcard handling:

const randomizer = (values) => {
    let i, pickedValue,
            randomNr = Math.random(),
            threshold = 0;

    for (i = 0; i < values.length; i++) {
        if (values[i].probability === '*') {
            continue;
        }

        threshold += values[i].probability;
        if (threshold > randomNr) {
                pickedValue = values[i].value;
                break;
        }

        if (!pickedValue) {
            //nothing found based on probability value, so pick element marked with wildcard
            pickedValue = values.filter((value) => value.probability === '*');
        }
    }

    return pickedValue;
}

Example usage:

let testValues = [{
    value : 'aaa',
    probability: 0.1
},
{
    value : 'bbb',
    probability: 0.3
},
{
    value : 'ccc',
    probability: '*'
}]

randomizer(testValues); // will return "aaa" in 10% calls, 
//"bbb" in 30% calls, and "ccc" in 60% calls;

Answer 3

Here's a faster way of doing that then other answers suggested...

You can achieve what you want by:

1. dividing the 0-to-1 segment into sections for each element based on their probability (For example, an element with probability 60% will take 60% of the segment).
2. generating a random number and checking in which segment it lands.

STEP 1

make a prefix sum array for the probability array, each value in it will signify where its corresponding section ends.

For example: If we have probabilities: 60% (0.6), 30%, 5%, 3%, 2%. the prefix sum array will be: [0.6,0.9,0.95,0.98,1]

so we will have a segment divided like this (approximately): [ | | ||]

STEP 2

generate a random number between 0 and 1, and find it's lower bound in the prefix sum array. the index you'll find is the index of the segment that the random number landed in

Here's how you can implement this method:

let obj = {
    "Common": "60",
    "Uncommon": "25",
    "Rare": "10",
    "Legendary": "0.01",
    "Mythical": "0.001"
}
// turning object into array and creating the prefix sum array:
let sums = [0]; // prefix sums;
let keys = [];
for(let key in obj) {
    keys.push(key);
    sums.push(sums[sums.length-1] + parseFloat(obj[key])/100);
}
sums.push(1);
keys.push('NONE');
// Step 2:
function lowerBound(target, low = 0, high = sums.length - 1) {
    if (low == high) {
        return low;
    }
    const midPoint = Math.floor((low + high) / 2);
  
    if (target < sums[midPoint]) {
        return lowerBound(target, low, midPoint);
    } else if (target > sums[midPoint]) {
        return lowerBound(target, midPoint + 1, high);
    } else {
        return midPoint + 1;
    }
}

function getRandom() {
    return lowerBound(Math.random());
}

console.log(keys[getRandom()], 'was picked!');

hope you find this helpful. Note: (In Computer Science) the lower bound of a value in a list/array is the smallest element that is greater or equal to it. for example, array:[1,10,24,99] and value 12. the lower bound will be the element with value 24. When the array is sorted from smallest to biggest (like in our case) finding the lower bound of every value can be done extremely quickly with binary searching (O(log(n))).

Answer 4

Here is a O(1) (constant time) algo to solve your problem.

Generate a random number from 0 to 99 (100 total numbers). If there are 40 numbers (0 to 39) in a given sub-range, then there is a 40% probability that the randomly chosen number will fall in this range. See the code below.

const number = Math.floor(Math.random() * 99); // 0 to 99
let element;

if (number >= 0 && number <= 39) {
    // 40% chance that this code runs. Hence, it is a bike.
    element = "bike";
}

else if (number >= 40 && number <= 69) {
    // 30% chance that this code runs. Hence, it is a car.
    element = "car";
}

else if (number >= 70 && number <= 84) {
    // 15% chance that this code runs. Hence, it is a boat.
    element = "boat";
}

else if (number >= 85 && number <= 94) {
    // 10% chance that this code runs. Hence, it is a train.
    element = "train";
}

else if (number >= 95 && number <= 99) {
    // 5% chance that this code runs. Hence, it is a plane.
    element = "plane";
}

Remember this, one Mathematical principle from elementary school? "All the numbers in a specified distribution have equal probability of being chosen randomly."

This tells us that each of the random numbers have equal probability of occurring in a specific range, no matter how large or small that range might be.

That's it. This should work!

Answer 5

I added my solution as a method that works well on smaller arrays (no caching):

    static weight_random(arr, weight_field){
    
        if(arr == null || arr === undefined){
            return null;
        }
        const totals = [];
        let total = 0;
        for(let i=0;i<arr.length;i++){
            total += arr[i][weight_field];
            totals.push(total);
        }
        const rnd = Math.floor(Math.random() * total);
        let selected = arr[0];
        for(let i=0;i<totals.length;i++){
            if(totals[i] > rnd){
                selected = arr[i];
                break;
            }
        }
    return selected;

}

Run it like this (provide the array and the weight property):

const wait_items =  [
    {"w" : 20, "min_ms" : "5000", "max_ms" : "10000"},
    {"w" : 20, "min_ms" : "10000", "max_ms" : "20000"},
    {"w" : 20, "min_ms" : "40000", "max_ms" : "80000"}
]   

const item = weight_random(wait_items, "w");
console.log(item);

Answer 6

ES2015 version of Radvylf Programs's answer

function getWeightedRandomItem(items) {
    const weights = items.reduce((acc, item, i) => {
        acc.push(item.weight + (acc[i - 1] || 0));
        return acc;
    }, []);
    const random = Math.random() * weights[weights.length - 1];
    return items[weights.findIndex((weight) => weight > random)];
}

And ES2022

function getWeightedRandomItem(items) {
    const weights = items.reduce((acc, item, i) => {
        acc.push(item.weight + (acc[i - 1] ?? 0));
        return acc;
    }, []);
    const random = Math.random() * weights.at(-1);
    return items[weights.findIndex((weight) => weight > random)];
}

Answer 7

I recently ran into this issue and solved it with a switch case, which is helpful because you can assign multiple "cases" to each element, thus weighting them.

I have a simple, common random number function which I run for the randomness:

const array = [el1, el2, el3];

const getWeightedElement = () => {
        switch (randNum(1, 10)) {
            case 10:
                return array[2];
            case 8:
            case 9:
                return array[1];
            default:
                return array[0];
        }
    }

You can change the values however you like, but the gist is that the switch rolls a random number from 1 to 10, and the cases determine that el3 has a 10% chance (1/10), el2 has a 20% chance, and for cases 1-7, el1 is the winner (70%).

if you want to weight a range of array elements in a larger array, you can just have the case run another random number to pick from the range instead of returning a fixed element. i.e.

...
case 1:
case 2:
case 3:
    return array[randNum(0, rangeMax)];

Answer 8

Sure you can. Here's a simple code to do it:

    // Object or Array. Which every you prefer.
var item = {
    bike:40, // Weighted Probability
    care:30, // Weighted Probability
    boat:15, // Weighted Probability
    train:10, // Weighted Probability
    plane:5 // Weighted Probability
    // The number is not really percentage. You could put whatever number you want.
    // Any number less than 1 will never occur
};

function get(input) {
    var array = []; // Just Checking...
    for(var item in input) {
        if ( input.hasOwnProperty(item) ) { // Safety
            for( var i=0; i<input[item]; i++ ) {
                array.push(item);
            }
        }
    }
    // Probability Fun
    return array[Math.floor(Math.random() * array.length)];
}

console.log(get(item)); // See Console.