Today I worked on a project which involved weighted randomization. In other words, I had to randomly choose an item from an array of weighted items. The items that were assigned a higher weight were to be more likely to be picked. The following is a JavaScript function that accomplishes just that:
/**
* Takes an array of items and an array of the corresponding weights and picks
* one of the items. The items with the higher weights are more likely to be
* picked.
* @param {!Array} items An array of items to choose from.
* @param {!Array.<number>} weights An array of non-negative integers with each
* number representing the likelihood of the number getting picked.
* @return {*} Returns one of the items from the array as long as at least one
* of the weights was a positive integer. Otherwise whatever is at
* items[-1] will be returned (this usually means undefined is returned).
*/
function pickUsingWeights(items, weights) {
var total = 0;
var ranges = weights.slice(0);
for(var i = 0, len = weights.length; i < len; i++) {
ranges[i] = [total, total += ranges[i]];
}
var randomNumber = parseInt(Math.random() * total);
for(;randomNumber < ranges[--i][0];);
return items[i];
}
Example
In my opinion, one of the best ways to understand how to use JavaScript (and other language for that matter) is by example, so here’s one:
// Prizes and the corresponding weights.
var prizes = ['PS4', 'DVD Player', 'Kit-Kat Bar', 'Nothing'];
var weights = [1, 2, 3, 94];
// Populate the prizesGiven object with zeroes for each prize.
var prizesGiven = {};
for(var i = 0; i < prizes.length; i++) {
prizesGiven[prizes[i]] = 0;
}
// Try using the pickUsingWeights function 1000 times to see
// how well the weighted randomization works.
var ATTEMPTS = 10000;
for(var i = 0; i < ATTEMPTS; i++) {
prizesGiven[pickUsingWeights(prizes, weights)]++;
}
// Show the results.
var msg = 'The results are as follows:';
for(var i = 0; i < prizes.length; i++) {
msg += '\r\n- ' + prizes[i] + ' was given out '
+ (100 * prizesGiven[prizes[i]] / ATTEMPTS).toFixed(2)
+ '% of the time.';
}
alert(msg);
You can click here to see the result of running the two preceeding blocks of code. As you can see, the percentages are close to the actual weights specified.
Function Description
This pickUsingWeights
function takes an array of items and an array of the corresponding weights and picks one of the items. The most likely items to be picked are those with the higher weights. Any item with a weight of zero has no chance of being picked.
Parameters
items {Array}
:
An array of items to choose from.weights {Array}
:
An array of non-negative integers with each number representing the likelihood of the corresponding item getting picked.
Returns
Returns one of the items from the items
array as long as at least one of the weights was a positive integer. Otherwise whatever is at items[-1]
will be returned (this usually means undefined
is returned).
Final Notes
If you are working on a project which involves picking items which are weighted feel free to use this function. 8)