Pick items from list with probability based upon property of list member ?

[Paul Rubin]

southof40 <shearichard at gmail.com> writes:
> I want to select an object from the list with a probability of : cars
> 0.7, bikes 0.3, trucks 0.1.

You can do it with one pass through the list using a well-known online
algorithm (I don't remember what it's called).  Untested code:

  import random
  tprob = 0   # total probability
  for x in vehicle_list:
     tprob += x.prob     # x.prob is 0.7, 0.3, 0.1, or whatever
     if random.uniform(0, tprob) <= x.prob:
        selected = x

To see why this works, use mathematical induction.  It's obviously right
if there is just one object in the list: tprob and x.prob are the same
thing, so the random number is always in range and that object gets
chosen.  And suppose it works correctly for n objects.  Then it also
works correctly for n+1 objects, since the (n+1)th object gets chosen
with the correct probility p, and with probability (1-p) one of the
earlier n objects is chosen, each with correct probability by the
induction hypothesis.  So by induction, it does the right thing for all n.

This uses one random number per item in the list, but Python's RNG is
pretty fast.  You can alternatively build a probability map or histogram
from the list (using more storage) and then select from it witn a single
call to the RNG.