Prev: Pick items from list with probability based upon property of list member ?
Next: [ANN] pyxser-1.4.4r --- Python Object to XML serializer/deserializer
From: Steven D'Aprano on 20 Jun 2010 10:24
On Sun, 20 Jun 2010 11:27:30 +0000, Mel wrote:

> southof40 wrote:
>
>> I have list of of N Vehicle objects - the only possible vehicles are
>> cars, bikes, trucks.
>>
>> I want to select an object from the list with a probability of : cars
>> 0.7, bikes 0.3, trucks 0.1.
>>
>> I've currently implemented this by creating another list in which each
>> car object from the original list appears 7 times, each bike 3 times
>> and each truck once. I then pick at random from that list.
>
> This seems about right. It's like a lottery where the more likely
> winners have more tickets, but all tickets are the same. Pick one to
> pick the winner.

It could be expensive to calculate though. Suppose the probabilities were:

0.608729
0.235012
0.156259


> There's a very expensive, but flexible technique that effectively gives
> some tickets a better chance than others. You have to examine each
> ticket individually, so this algorithm burns random numbers like
> kindling:
>
>
>
> import random
>
> #===============================
> def weighted_choice (candidates, weight):
> chosen = None
> total = 0
> for c in candidates:
> w = weight (c)
> total += w
> if random.randint (0, total-1) < w:
> chosen = c
> return chosen
> #===============================

Nice! But instead of randint(0, total-1), you can use randrange(0, total).

This only requires N random numbers (for N candidates), which isn't
really that excessive, but we can do better, and support non-integer
weights as well.

def weighted_choice(candidates, weights):
"""Choose between a list of candidates with a list of weights."""
cumulative_weights = []
running_total = 0
for w in weights:
running_total += w
cumulative_weights.append(running_total)
x = random.uniform(0, running_total)
for item, cw in zip(candidates, cumulative_weights):
if x <= cw:
return item

This is O(N) on the number of candidates, and requires one call to random
no matter what N is.



--
Steven
 | 
Pages: 1
Prev: Pick items from list with probability based upon property of list member ?
Next: [ANN] pyxser-1.4.4r --- Python Object to XML serializer/deserializer