python - Random weighted choice

Question

I have data like this:

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 pretty way to choose id2 if I know id1, using priority?

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

Percent will be rough of course

Answer 1

Generate 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 generate a random number and search for 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