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.