How to choose a weighted random array element in Javascript?
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;
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.