Categories:
 

Algorithm for generating weighed random numbers

There are many techniques for generating weighed random numbers, and for an exhausted list, consult "Statistics meets Linear Algebra 808". For the rest of us, a very popular method is also a very simple one, which is what we'll look at here.

What we need first is a set of random items to work with; instead of numbers, lets use something more meaningful, like fruits:

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

Now for the moment of truth. Since rarely do people like all fruits equally, we shall 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%].

Now to the algorithm that connects the two arrays, and makes each fruit show up x percentage of the time as denoted by their weight divided by total weight. The basic idea is quite simple. We loop through array fruits[], and for each element (ie: Apples), put it into a new array the number of times its weight. For example, "Apples" has a weight of two, so we'll put it into the new array twice. The result is:

var fruits=["Apples", "Oranges", "Grapes", "Bananas"]
var fruitweight=[2, 3, 1, 4] //weight of each element above
var totalweight=eval(fruitweight.join("+")) //get total weight (in this case, 10)
var weighedfruits=new Array() //new array to hold "weighted" fruits
var currentfruit=0

while (currentfruit<fruits.length){ //step through each fruit[] element
	for (i=0; i<fruitweight[currentfruit]; i++)
		weighedfruits[weighedfruits.length]=fruits[currentfruit]
	currentfruit++
}

With all the loops running around, it may take a bit of starring before you realize what's going on. Basically we use an outer while loop to step through each of array fruit[]'s elements (4 steps in total), then for each element, populate the array weighedfruits[] with it the number of times the element's weight. So what have we accomplished? A lot, actually. The new array weighedfruits[] now contains duplicate copies of each of the original array's elements as laid out by their weight. A little thinking tells us this means the likelihood of each element getting randomly selected has also changed per its weight.

We can proceed to displaying a random fruit- but with weight added in- by merely generating a random number within the bounds of the new array and using it as the index:

var randomnumber=Math.floor(Math.random()*totalweight)
document.write(weighedfruits[randomnumber])

Viola! "Apples" should now show up roughly 20% of the time, Oranges 10%, and so on when the page is loaded.

Conclusion

The above algorithm can be used inside any of your random scripts that require "weight control." In fact, a similar technique is used not just in JavaScript, but many relevant Perl and PHP scripts.

Have fun keeping tabs on your random scripts' weight!