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

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.

Answer 2

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

function weighted_random(items, weights) {
    var i;

    for (i = 0; i < weights.length; i++)
        weights[i] += weights[i - 1] || 0;
    
    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 = [];

    for (i = 0; i < options.length; i++)
        weights[i] = options[i].weight + (weights[i - 1] || 0);
    
    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 3

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 4

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 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);