Probability selection algorithm

Noah noah at noah.org
Sat Feb 1 17:43:29 EST 2003


I'm chewing over a little algorithm problem. It's a simple problem.
Given a list of probabilities, what is the simplest way to randomly select
one of the items from the list based on that item's probability?
For example, here are some lists of probabilities:
    [0.2, 0.2, 0.2, 0.2, 0.2]
        items all have equal chance of getting selected (20%)
    [0.33, 0.33, 0.33]
        items all have equal chance of getting selected (33%)
    [0.33, 0.66]
        item 1 is twice as likely to get selected as item 0.
    [0.46, 0.27, 0.27]
        item 0 has slightly less than 50% chance of selection...
    [0.17, 0.62, 0.21]
        items have all unequal chances of selection.

I can generate a random number between 0.0 and 1.0,
but how do I turn that into an index into a given list?
I was thinking that I could convert the lists of probabilities
into lists of probability ranges. Then I would choose a random number
between 0 and 1 and then select the item that falls in that range.
For example the last list [0.17, 0.62, 0.21] would be converted to
[0.17,  0.79,  1.0]
    if the random number is in the range 0.0-0.17 then select the first item.
    if the random number is in the range 0.17-0.79 then select the second item.
    if the random number is in the range 0.79-1.0 then select the third item.

That seems like a crufty algorithm. There must be a simpler way.

Yours,
Noah




More information about the Python-list mailing list