implement random selection in Python

[mensanator at aol.com]

On Nov 15, 10:40�pm, Bruza <benr... at gmail.com> 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

What do you think of this?

import random
N = 100
items = [('Mary',30), ('John', 10), ('Tom', 45), ('Jane', 15)]
the_items = []
for i,j in items:
  the_items.extend([i]*j)
histogram = {}
for i in xrange(N):
  chosen = random.choice(the_items)
  print chosen,
  if chosen in histogram:
    histogram[chosen] += 1
  else:
    histogram[chosen] = 1
print
print
for i in histogram:
  print '%4s: %d' % (i,histogram[i])

##  John Mary Jane Tom Tom Mary Mary Tom John John Tom John Tom
##  John Mary Mary Mary John Tom Tom John Mary Mary Tom Mary
##  Mary John Tom Jane Jane Jane John Tom Jane Tom Tom John Tom
##  Tom Mary Tom Tom Mary Tom Mary Tom Tom Tom Tom Mary Mary Tom
##  Mary Tom Mary Tom Tom Jane Tom Mary Tom Jane Tom Tom Tom Tom
##  Tom Mary Tom Jane Tom Mary Mary Jane Mary John Mary Mary Tom
##  Mary Mary Tom Mary John Tom Tom Tom Tom Mary Jane Mary Tom
##  Mary Tom Tom Jane Tom Mary Mary Tom
##
##  Jane: 11
##  John: 12
##  Mary: 32
##   Tom: 45