Random Weighted Choice

Question

I have the following data:

d = ( (701, 1, 0.2), (701, 2, 0.3), (701, 3, 0.5), (702, 1, 0.2), (702, 2, 0.3), (703, 3, 0.5) ) 

Where (701, 1, 0.2) = (id1, id2, priority)

Is there a good way to select id2 if I know id1 using priority?

Func (701) should return:
1 - in 20% of cases
2 - 30%
3 - 50%

The percentage will be rude, of course.

Answer 1

Create a cumulative distribution function for each ID1, thus:

 cdfs = defaultdict() for id1,id2,val in d: prevtotal = cdfs[id1][-1][0] newtotal = prevtotal + val cdfs[id1].append( (newtotal,id2) ) 

So you will have

 cdfs = { 701 : [ (0.2,1), (0.5,2), (1.0,3) ], 702 : [ (0.2,1), (0.5,2) ], 703 : [ (0.5,3) ] } 

Then create a random number and find it in the list.

 def func(id1): max = cdfs[id1][-1][0] rand = random.random()*max for upper,id2 in cdfs[id1]: if upper>rand: return id2 return None 

Answer 2

Realizing that my first answer was rather difficult in his math, I created a new idea. I find the algorithm here is similar to the algorithm of some other answers, but this implementation seems to be suitable for the “pretty” (if it matches a simple) requirement of the question:

 def func(id): rnd = random() sum = 0 for row in d: if row[0] == id: sum = sum + row[2] if rnd < sum: return row[1] 

In the sample data from OP, it looks like this:

• Choose a random number from 0 to 1.0
• If the number < 0.2 returns the first element
• If number < 0.5 returns the second element
• Else (if number < 1.0 ) returns the third element

Answer 3

Use a discrete uniform distribution from a random module over a sufficient number of values, then divide it:

For example, for case 701, use a distribution of 10 values, for 2 values, return 1, for another 3, return 2, and for the remaining 5, return 3.

You can build any distribution using fairly uniform distributions :)

Answer 4

If your percentages will not be more accurate than integer percentages, use a random number generator to generate the number 0-99.

Then in your function, use (software) cases to select the correct number. For example (clear this):

 if 701
   if random_num <20
     return 1
   else if random number <50 // (20 + 30)
     return 2
   else if random number <100 // (20 + 30 + 50)
     return 3
   else
     // error

Answer 5

Very fast hack:

 import random d = { 701: [(1,0.2),(2,0.3),(3,0.5)], 702: [(1,0.2),(2,0.3),(3,0.5)] } def func(value): possible_values=d[value] total=sum(p[-1] for p in possible_values) random_value=random.random() prob=possible_values[0][-1]/total index=1 while index<len(possible_values) and prob<random_value: prob+=possible_values[index][-1]/total index+=1 return possible_values[index-1][0] if __name__=='__main__': testcases=1000 cnt=[0,0,0] for case in xrange(testcases): answer=func(701) cnt[answer-1]+=1 for i in xrange(3): print "Got %d %f%% of the time"%(i+1,float(cnt[i])/testcases*100) 

It's ugly, but it's the first thing that comes to mind, and seems to work as expected.

This is done to obtain a random value in the interval [0,1) (using random.random ()). He then uses whether the random value falls into the intervals [0,0,2), [0,2,0,5) or [0,5,1) to figure out which value to return.

Answer 6

Two ideas (let me illustrate this with separate parameters and relationships for clarity in the argument names, if they are packed in a tuple, you can save the "zip"):

a) Denormalize the weights to get the whole relationship, then put as many copies as the ratio on the list and use random.choice .

 def choice_with_ratios(options, ratios): tmp = sum([[v]*n for v, n in zip(options, ratios)], []) return random.choice(tmp) 

b) Use normalized weights and start summing until you reach an arbitrarily generated uniform value

 def choice_with_weights(options, weights): s = 0 r = random.random() for v, w in zip(options, weights): s += w if s >= r: break return v 

By the way, if the first field is used as a key, you should have it in the dictionary, for example:

 d = { 701: ((1, 0.2), (2, 0.3), (3, 0.5), 702: ((1, 0.3), (2, 0.2), (3, 0.5) } 

Answer 7

You can also create a list of 100 elements for each value, and then let random.choice make a choice from the visited list, whose members are loaded in the desired weight:

 import random from collections import defaultdict d = ( (701, 1, 0.2), (701, 2, 0.3), (701, 3, 0.5), (702, 1, 0.2), (702, 2, 0.3), (702, 3, 0.5) ) class WeightedLookup(object): def __init__(self, valueTupleList): self.valdict = defaultdict(list) for key, val, prob in valueTupleList: self.valdict[key] += [val]*(int)(prob*100) def __getitem__(self,key): return random.choice(self.valdict[key]) lookup = WeightedLookup(d) # test out our lookup distribution, sample it 100000 times res = { 1:0, 2:0, 3:0 } for i in range(100000): res[lookup[701]] += 1 # print how many times each value was returned for k in (1,2,3): print k, res[k] 

Print

 1 20059 2 30084 3 49857