implement random selection in Python

[duncan smith]

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

I think you need to clarify what you want to do.  The "probs" are
clearly not probabilities.  Are they counts of items?  Are you then
sampling without replacement?  When you say N < len(items) do you mean N
<= sum of the "probs"?

Duncabn