Probability selection algorithm

[Mike C. Fletcher]

Take the total of the entire set, do your random call, then use a 
function such as indexOf below to get the index. There are probably 
nicer approaches (such as using bisect on a list of transition-points), 
but this should work fine.

import operator
def total( probset ):
    return reduce( operator.add, probset )
def enumerate( probset ):
    return map( None, range(len(probset)), probset)
def indexOf( value, probset ):
    """Get index of value in probset

    value -- float value
        values < 0 will return index 0
        values > total(probset) will return len(probset)
    probset -- sequence of partial float probabilities
    """
    index = 0
    for i,v in enumerate(probset):
        value = value-v
        if value <= 0:
            return i
    return len(probset)


Enjoy,
Mike

Noah wrote:

>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
>  
>

-- 
_______________________________________
  Mike C. Fletcher
  Designer, VR Plumber, Coder
  http://members.rogers.com/mcfletch/