随机加权选择

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

使用Python的随机模块中的离散均匀分布，选择足够多的值，然后进行分组：

举个例子，对于701这个情况，可以在10个值中进行分布。比如，2个值返回1，另外3个值返回2，还有5个值返回3。

你可以通过足够多的均匀分布来构建任何你想要的分布哦 :)

Answer 2

意识到我之前的回答在数学上有不少错误，我想出了一个新的想法。我认为这里的算法和其他一些答案类似，但这个实现看起来更符合问题中提到的“简单美观”的要求：

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]

根据提问者提供的示例数据，步骤如下：

• 随机选择一个介于0和1.0之间的数字
• 如果这个数字小于 0.2，就返回第一个元素
• 如果这个数字小于 0.5，就返回第二个元素
• 否则（如果这个数字小于 1.0），就返回第三个元素

Answer 3

为每个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