Javascript: weighted random value from array

There are many techniques for generating weighed random numbers. Some time ago I have looked for some ready to use Javascript solution and found the code that generates bigger array with duplicated elements with values from the original values array in a proportion described by weight array.

For example, lets define array of fruits:

var fruits=["Apples", "Oranges", "Grapes", "Bananas"]

Now we will assign a weight to each fruit, using another literal array just for consistency:

var fruitweight=[2, 3, 1, 4]

There is nothing complicated about "fruitweight" at this point- it merely holds 4 numbers, each pertaining to their respective fruits above. However, it is these numbers we'll be using to signal the weight of each fruit. Considering they add up to 10, another way of looking at fruitweight is [20%, 30%, 10%, 40%].

For the algorithm that I have found and this data new generated array will look like this:

var tmp = {0:"Apples", 1:"Apples", 2:"Oranges", 3:"Oranges", 4:"Oranges", 5:"Grapes", 6:"Bananas", 7:"Bananas", 8:"Bananas", 9:"Bananas"};

It is quite clear that accessing this array with the random index will return weighted random values from the array. And it is quite clear that it will work quite fast, but only for small ranges and small integer weights. If set of values will be big enough or weights will contain float values algorithm will require lot of resources and can even be slow.

So, to solve the problem I have implemented another old algorithm that I have described in one of my previous articles about weighted random row selection from MySQL database table. It does not require lot of memory. However it requires some preparation steps, but much less iterations than in previous algorithm. I think code will explain everything:

var fruits=["Apples", "Oranges", "Grapes", "Bananas"]
var fruitweight=[2, 3, 1, 4] //weight of each element above
var fruitweight_norm = new Array() //normalized weights
var currentfruit=0

var sum = 0;
for (i=0; i<fruits.length; i++){
	sum += fruitweight[i];
	fruitweight_norm[i] = sum;
}

for (i=0; i<fruits.length; i++){
	fruitweight_norm[i] = fruitweight_norm[i]/sum;
}

function get_rand(){
	var rand = Math.random();
	var prev = 0;
	for (i=0; i<fruits.length; i++){
		document.write("Random range - "+prev+" : "+fruitweight_norm[i]+"<br>");
		if((prev<rand)&&(fruitweight_norm[i]>rand)){
			return i;
		}
		prev = fruitweight_norm[i];
	}
}

function get_fast(){
    needle = Math.random();
    high = fruitweight_norm.length - 1;
    low = 0;
    
    while(low < high){
        probe = Math.ceil((high+low)/2);
        
        if(fruitweight_norm[probe] < needle){
            low = probe + 1;
        }else if(fruitweight_norm[probe] > needle){
            high = probe - 1;
        }else{
            return probe;
        }
    }
    
    if(low != high ){
        return (fruitweight_norm[low] >= needle) ? low : probe;
    }else{
        return (fruitweight_norm[low] >= needle) ? low : low + 1;
    }
}

If you are interested to run some test, you may use the following code that I have used to test it during the programming:

tmp = [0,0,0,0];

for (i=0; i<1000; i++){
	id = get_fast();
	tmp[id] += 1;
}

for (i=0; i<4; i++){
	document.write("Randoms - "+i+" = "+tmp[i]+"<br>");
}

This will allow to see that values are generated randomly according to the weights. You may also notice that code works quite fast.

Hope this article and code will be useful for somebody. Let me know you have notice som mistake and do not forget to follow my blog.

Posted by:
Enjoyed this post? Share and Leave a comment below, thanks! :)