（Python）基于比例/权重随机选择键的算法

Question

我有点困惑，不知道怎么找到一个简单的算法来完成以下任务：

假设我有一个字典 k：

>>> k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}

现在我想根据这些键在总数中的“权重”随机选择一个键。

>>> sum(k.values()) 
>>> 274

也就是说，A 被选中的概率是

>>> 68.0/274.0
>>> 0.24817518248175183

24.81%。

你会怎么写一个算法来实现这个？换句话说，确保在 10,000 次随机选择中，A 会被选中 2.481 次？

Answer 1

这个算法是这样的……

首先，随机选择一个1到274之间的数字。为了做到这一点，可以调用一个叫做rand()的函数（假设它返回一个0到1之间的值），然后把这个值乘以274。这样得到的结果就会在一个范围内。如果结果在1到68之间，就选择A；如果在69到130之间，就选择B，依此类推。这样一来，你的概率就能保持有效，操作也能成功。

PS：我比较熟悉Java，不太懂Python的语法。

Answer 2

这段代码应该能解决问题：

>>> k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}
>>> import random
>>> def weighted_pick(dic):
...     total = sum(dic.itervalues())
...     pick = random.randint(0, total-1)
...     tmp = 0
...     for key, weight in dic.iteritems():
...         tmp += weight
...         if pick < tmp:
...             return key

Answer 3

这里有一个加权选择的函数，还有一些代码来演示它的用法。

import random

def WeightedPick(d):
    r = random.uniform(0, sum(d.itervalues()))
    s = 0.0
    for k, w in d.iteritems():
        s += w
        if r < s: return k
    return k

def Test():
    k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}
    results = {}
    for x in xrange(10000):
        p = WeightedPick(k)
        results[p] = results.get(p, 0) + 1
    print results

Test()