Today seemed like a dull day at the keyboard. I beat my head against Objective C a lot. And, I implemented a weighted random choice which I have done a thousand times before. Dull, right?
I needed a weighted random choice in two different places, and I implemented it differently in each place. Weird, right? Even weirder, I think I did the right thing in each place.
Picking a card from a deck
In the first case, I needed to choose a flash card from a deck. I want to favor cards that have given the player trouble in the past. I zip through the list once to sum up the weights. Then, I pick a random number greater or equal to zero and less than the sum of the weights. Then, I run through the list again summing the weights until my running sum exceeds my random number. (Here in Perl, um, for clarity?):
foreach my $item ( @list_of_items ) {
$total += weight( $item );
}
my $thresh = rand( $total );
my $found;
foreach my $item ( @list_of_items ) {
$thresh -= weight( $item );
if ( $thresh < 0.0 ) {
$found = $item;
last;
}
}
This requires that the weight() of a given item remains constant for the duration of the function. The weight() can change between choices, however. If the weight() will remain constant for large portions of the program then you can cache the total and only bother with the second half of the loop.
Choosing a letter of the alphabet
In a different portion of the program, I need to make random letter tiles. I feel like there should be more E‘s than Q‘s. I also want to leave a pathway to use the same artwork for different languages. Because of all of this, I opted to have the weights to come in from a file.
My data file is JSON encoded. I could, I suppose, do something like this (given the English letter frequencies):
"english" : {
"A": 8.167,
"B": 1.492,
"C": 2.782,
...
}
}
But, that hurts to even think about. Instead, I opted to round them off to integer proportions. Then, I could just do this:
"english": "AAAAAAAABBCCC..."
}
Now, making a random choice simply involves selecting one character from the string.
[…] my previous post, I wrote some code in Perl because I wanted the code to be clear and obvious. Wait? What? Who uses […]
Hello Patrick,
I have a question regarding your post on “weighted random choice” dated May 5th, 2009.
Does your first implementation (the one for picking a card from a deck) also works when dealing with real numbers? In other words, the weights that I have are real numbers (e.g., 1/distance, in which the distance is in meters).
I used the algorithm for a simple example on paper and it seems it works for weights with real values. Please let me know if I am right.
Thank you very much in advance.
Yes. It works as long as you have a finite list of non-negative real weights. In your case, as long as you have a finite list of positive distances.
Technically, it works even if you’ve got a countably infinite list where you know the sum in advance so you can skip the first loop. But, yes… for a finite list, it will work fine.