随机加权选择

Question

我有这样的数据：

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)

)

其中（701，1，0.2）=（id1，id2，优先级）

如果我知道ID1，是否有使用优先级选择ID2的好方法？

Func（701）应该返回：

  1-在20％的情况下

  2-30％

  3-50％

百分比当然是粗糙的

Answer 1

因此，为每个ID1生成一个累积分布函数：cdfs = defaultdict()for id1,id2,val in d:    prevtotal = cdfs[id1][-1][0]    newtotal = prevtotal + val    cdfs[id1].append( (newtotal,id2) )所以你会有cdfs = { 701 : [ (0.2,1), (0.5,2), (1.0,3) ],          702 : [ (0.2,1), (0.5,2) ],         703 : [ (0.5,3) ] }然后生成一个随机数并在列表中搜索。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

意识到我的第一个答案在数学上有很多错误，我提出了一个新的主意。我相信这里的算法类似于其他几个答案的算法，但是这种实现似乎可以满足问题的“漂亮”（如果相等）的要求：def func(id):&nbsp; &nbsp; rnd = random()&nbsp; &nbsp; sum = 0&nbsp; &nbsp; for row in d:&nbsp; &nbsp; &nbsp; &nbsp; if row[0] == id:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum = sum + row[2]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if rnd < sum:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return row[1]使用OP中的示例数据，结果如下：选择一个介于0到1.0之间的随机数如果数字< 0.2返回第一个元素否则，如果数字< 0.5返回第二个元素否则（如果数字为< 1.0），则返回第三个元素