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