implement random selection in Python

Bruza benruza at gmail.com
Fri Nov 16 05:40:36 CET 2007


I need to implement a "random selection" algorithm which takes a list
of [(obj, prob),...] as input. Each of the (obj, prob) represents how
likely an object, "obj", should be selected based on its probability
of
"prob".To simplify the problem, assuming "prob" are integers, and the
sum of all "prob" equals 100. For example,

   items = [('Mary',30), ('John', 10), ('Tom', 45), ('Jane', 15)]

The algorithm will take a number "N", and a [(obj, prob),...] list as
inputs, and randomly pick "N" objects based on the probabilities of
the
objects in the list.


For N=1 this is pretty simply; the following code is sufficient to do
the job.

def foo(items):
    index = random.randint(0, 99)
    currentP = 0
    for (obj, p) in items:
       currentP += w
       if currentP > index:
          return obj

But how about the general case, for N > 1 and N < len(items)? Is there
some clever algorithm using Python standard "random" package to do
the trick?

Thanks,

Ben



More information about the Python-list mailing list