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
--
http://mail.python.org/mailman/listinfo/python-list
