 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!
|
