Choosing Random Weighted Object from an Array

Question

I'm trying to figure out a way to choose a random object from an array, based on it's weight property. Here's an example array:

var item = [{
 verDiv: 'div-gpt-ad-1553003087342-0',
 verKv: 'version1',
 verSize: [300, 250],
 weight: 10 //should be chosen in 10% of cases
},
{
 verDiv: 'div-gpt-ad-1553003087342-1',
 verKv: 'version2',
 verSize: [300, 250],
 weight: 25 //should be chosen in 25% of cases
},
{
 verDiv: 'div-gpt-ad-1553003087342-2',
 verKv: 'version3',
 verSize: [160, 600],
 weight: 25 //should be chosen in 25% of cases
},
{
 verDiv: 'div-gpt-ad-1553003087342-3',
 verKv: 'version4',
 verSize: [728, 90],
 weight: 40 //should be chosen in 40% of cases
}];

What I want to do is choose one of the four objects by using a function, which takes their weight properties into account, so I can then call the other properties where needed.

console.log([item[weightFunction()].verDiv]);
console.log([item[weightFunction()].verKv]);
console.log([item[weightFunction()].verSize]);

EDIT:The above is just a suggestion, I'm sure there are better ways to do it.

• nick zoum: Doing weightFunction(item) would make more sense

Answer 1

Assuming the sum of all weights is exactly 100 (otherwise calculate it and use as cumul initial value and random multiplier:

function weightFunction(items) {
 var cumul = 100
 var random = Math.floor(Math.random() * 100)
 for(var i = 0; i < items.length; i++) {
 cumul -= items[i].weight
 if (random >= cumul) {
 return items[i]
 }
 }
}

• Lyubomir Shishkov: Thank you very much. Works like a charm :)
• Lyubomir Shishkov: EDIT: When I start calling the different properties weightFunction(item).verDiv weightFunction(item).verKv It returns values from different objects :C
• wang: weightFunction will return random item every time you call it. weightFunction(item).verDiv and weightFunction(item).verKv are two calls. you have to store it like var choosen = weightFunction(item) and use it as choosen.verDiv and choosen.verKv
• gbalduzzi: Yep, exactly as undefined said. It is not random if it returns the same everytime ;)

Answer 2

You could take a closure over the weight array with all weights and return a function which gets the index based on the sum of all weights.

function getWeightedDistribution(weights) {
 return function () {
 var random = Math.random(),
 sum = 0;
 return weights.findIndex(w => random < (sum += w));
 };
}
var weights = [0.1, 0.25, 0.25, 0.4], // all values have to sum to 1
 i;
 weightFunction = getWeightedDistribution(weights),
 counts = [0, 0, 0, 0];
for (i = 0; i < 1e6; i++) counts[weightFunction()]++;
console.log(...counts);

Together with your code

function getWeightedDistribution(weights) { // weights sums up to 1
 return function () {
 var random = Math.random(),
 sum = 0;
 return weights.findIndex(w => random < (sum += w));
 };
}
var item = [{ verDiv: 'div-gpt-ad-1553003087342-0', verKv: 'version1', verSize: [300, 250], weight: 10 }, { verDiv: 'div-gpt-ad-1553003087342-1', verKv: 'version2', verSize: [300, 250], weight: 25 }, { verDiv: 'div-gpt-ad-1553003087342-2', verKv: 'version3', verSize: [160, 600], weight: 25 }, { verDiv: 'div-gpt-ad-1553003087342-3', verKv: 'version4', verSize: [728, 90], weight: 40 }],
 weightFunction = getWeightedDistribution(item.map(({ weight }) => weight / 100));
console.log(item[weightFunction()].verDiv);
console.log(item[weightFunction()].verKv);
console.log(item[weightFunction()].verSize);

Answer 3

This is a more abstract approach to the problem, that allows the total weight to be above 100 and you can define how the weight property for each element will be retrieved.

The way this works is by creating a map of the ranges for each value and it returns the first element whose range 'caught' the random number.

var item = [{
 verDiv: 'div-gpt-ad-1553003087342-0',
 verKv: 'version1',
 verSize: [300, 250],
 weight: 10 //should be chosen in 10% of cases
 },
 {
 verDiv: 'div-gpt-ad-1553003087342-1',
 verKv: 'version2',
 verSize: [300, 250],
 weight: 25 //should be chosen in 25% of cases
 },
 {
 verDiv: 'div-gpt-ad-1553003087342-2',
 verKv: 'version3',
 verSize: [160, 600],
 weight: 25 //should be chosen in 25% of cases
 },
 {
 verDiv: 'div-gpt-ad-1553003087342-3',
 verKv: 'version4',
 verSize: [728, 90],
 weight: 40 //should be chosen in 40% of cases
 }
];
function weightFunction(list, getWeight) {
 var total = 0; // Faster than doing another loop with reduce
 var map = list.reduce(function(result, value, index) {
 var currentWeight = getWeight(value, index);
 total += currentWeight;
 result[total] = value;
 return result;
 }, {});
 var random = Math.random() * total;
 return map[Object.keys(map).find(function(index) {
 return index >= random;
 })];
}
console.log(weightFunction(item, x => x.weight).verDiv);
console.log(weightFunction(item, x => x.weight).verKv);
console.log(weightFunction(item, x => x.weight).verSize);

Answer 4

• define an array called stat_map which will have size of sum of all weights eventually
• populate stat_map with indices of items so that stat_map contains indices of items as much as its weight.
• now stat_map contains 10 0(index of first item), 25 1(index of second item), 25 2(index of third item), 40 3(index of forth item)
• if you pick random element from stat_map, it will be the index of choosen item and it's obvious that item's will be picked according to their weight.

const item = [{
 verDiv: 'div-gpt-ad-1553003087342-0',
 verKv: 'version1',
 verSize: [300, 250],
 weight: 10 //should be chosen in 10% of cases
},
{
 verDiv: 'div-gpt-ad-1553003087342-1',
 verKv: 'version2',
 verSize: [300, 250],
 weight: 25 //should be chosen in 25% of cases
},
{
 verDiv: 'div-gpt-ad-1553003087342-2',
 verKv: 'version3',
 verSize: [160, 600],
 weight: 25 //should be chosen in 25% of cases
},
{
 verDiv: 'div-gpt-ad-1553003087342-3',
 verKv: 'version4',
 verSize: [728, 90],
 weight: 40 //should be chosen in 40% of cases
}];
const randomItem = (item) => {
 const stat_map = []
 item.map((v, i) => stat_map.push(...new Array(v.weight).fill(i)))
 const rand = Math.floor(Math.random() * stat_map.length)
 return item[stat_map[rand]]
}
console.log(randomItem(item))