Probability selection algorithm

[Paul Rubin]

noah at noah.org (Noah) writes:
> 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.

Try something like:

    remaining = 1.0
    for i range(len(problist)):
       if urand() < remaining:
         selected = i
       remaining -= problist[i]

where urand returns a random number between 0.0 and 1.0 and
problist is your list of probabilities.  "selected" is set to
the appropriate randomly chosen index.

Do I have that right?