How to Make a Weighted Random Choice May 5th, 2009
Patrick Stein

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?):

my $total = 0.0;
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.

l