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
]

Solution 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.

Solution 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;
}

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

Solution 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))).

View more solutions

Comments

[Bill the Lizard]

Possible duplicate of Generate A Weighted Random Number

[mattsoave]

This works reasonably well for small integers (which was also my use case), but since it works by creating a new array with a length equal to the sum of the weights, it could become huge/slow with high numbers. It also doesn't work for non-integers, so you would need to find the lowest common denominator to get to an integer (which may not be possible for very precise weights).

[Radvylf Programs]

@mattsoave Yeah, this is already several thousand times slower than the second answer, and that's with five options.

[JJJ]

You might want to clarify what "answer #2" is. Answers are ordered by votes so their order can change. People can also have a different sorting for answers (e.g. by oldest first.)

[Radvylf Programs]

Just to clarify: The for loop one is the fastest, but less readable. This solution, at 200,000 ops/sec, isn't terribly slow either.

[Yukulélé]

sum is useless while acc have the same value

[Yukulélé]

the last line can be simplified: return items[chances.findIndex(el => el > rand)]

[Benoît]

That looks awesome ! Any chance you have an idea on how to adapt that to a 2 dimensional array efficiently ? :)

[Radvylf Programs]

@Benoît Assuming you just want to pick an item in the 2-dimensional array using another 2-dimensional array for the chances, you can just add the lines items = items.flat() and chances = chances.flat() at the top of the function (or, for IE compatibility, items = [].concat.apply([], items) and chances = [].concat.apply([],chances)

[O'Neill]

Make sure to have your values already sorted by probability

[matt]

This method is hard to read because you have to mentally match up the value in items with the number in chances. If you have more than a few elements, it's going to be a bear to debug.

[Radvylf Programs]

@matt I could design a version that uses an array of objects with the properties item and weight, if you want

[matt]

Thanks for responding; your second way does look better for larger problems. I had come up with my own version which was a mishmash of the approaches here, which I think ended up being basically the same as your second version.

[Leigh Cheri]

ES6 and var? better to use let!

[Radvylf Programs]

@LeighCheri One of my main goals here was browser compatiblity, so I dropped the ES6 stuff like let.

[Yash]

running this sometimes also selects an element which has 0 weight, i ran a loop of 100, a 0 weight element gets picked about 2-7 times

[Radvylf Programs]

@Yash I cannot reproduce this, and if you look at the way this works it's impossible for that to occur. Are you sure you're providing the inputs correctly?

[Jon]

I'm sorry, this is helpful but could you please provide an example of it being used too?

[Jon]

Code doesn't return based on probability defined - I ran it 100,000 times and got 0 common, 5990 uncommon, 25144 rare, etc.

[atanay]

the 0 at the start is not part of the keys, it's 59900 common, 25144 uncommon etc.

[Envayo]

Would having weights as 30, 40, 15 compared to 0.30, 0.40, 0.15 make a difference? In the first case the total would be 100, and in the second case the total would be 1. It doesn't seem to be making a difference, just wondering...

[Radvylf Programs]

@Envayo Nope, no difference. It bases it off of the sum of the weights, so you can scale it however you want.

[user3871]

@RadvylfPrograms Hi. This is awesome, but I'm trying to understand how and why it works. 1) why do you add the previous element's weight to the current element in weights[i] = options[i].weight + (weights[i - 1] || 0);, and 2) why do you multiply random * last weight in array and use it to which weights[i] is > than that random?

[Radvylf Programs]

@user3871 All good questions! I've added an explanation of how it works to the answer, hopefully it helps. The reason I add all of the previous elements to the weights is that it does two steps in one, since the last element becomes the sum of the weights, which you need in order to pick a random item.

[user3871]

@RadvylfPrograms clever. I like it. I used to do this by loading the element into the array n times (where n is its probability * 10) and randomly select from array. So, to be clear, you're multiplying "random" * sum of weights because its product gives a value we can use to determine which probability of the elements is greater than or equal to it (ie its chance)? Secondly, in your chart, shouldn't the first line be 5, and not 6?

[Radvylf Programs]

@user3871 The approach with adding the element n times works, but it gets slow with large arrays and doesn't work with fractional weights like 0.25 or 1.18. You're correct about what the random number is doing. In the chart, I started the random numbers at 6 mostly just as a random starting point, the random number could be anything from 0 to 17 so I only chose some values that would be enough demonstrate how it works.

[Matteobikk90]

amazing method, is there any chance to avoid duplicates?

[Radvylf Programs]

@LovelyWeather89 You can use a for loop going over the array backwards, checking if i (the for loop variable) is equal to items.indexOf(items[i]). If it's not, that means the item at i is a duplicate. And then you just need to .push any non-duplicate items and their weights into empty arrays. Something like this.

[Matteobikk90]

@RadvylfPrograms, Hi thanks a lot, still what I would like to archieve is to return an array of 20 elements with no duplicates, the code above freeze the page, maybe I implemented that in a wrong way

[Radvylf Programs]

@LovelyWeather89 Oh my mistake, the i++ should be i--, and the > should be >=. If you just want to remove duplicates in an ordinary array though, instead of the items/weights used in this answer, you can do Array.from(new Set(x)) where x is the array to remove duplicates from.