implement random selection in Python

Bruza benruza at gmail.com
Fri Nov 16 07:42:22 CET 2007


On Nov 15, 9:32 pm, "mensana... at aol.com" <mensana... at aol.com> wrote:
> 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

No. That does not solve the problem. What I want is a function

  def randomPick(n, the_items):

which will return n DISTINCT items from "the_items" such that
the n items returned are according to their probabilities specified
in the (item, pro) elements inside "the_items".

If I understand correctly, both of the previous replies will output
one item at a time independently, instead of returning n DISTINCT
items at a time.




More information about the Python-list mailing list