implement random selection in Python

[James Stroud]

Bruza wrote:
> 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

This will not get you an A on your homework:

x = []
[x.extend([i]*n) for (i,n) in items]
random.choice(x)

James


-- 
James Stroud
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA  90095

http://www.jamesstroud.com