in [Python]

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 |