python - (Python) 基于比例/权重随机选择 key 的算法

Question

对于如何找到一个干净的算法来执行以下操作，我有点不知所措:

假设我有一个字典 k:

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

我现在想随机选择这些 key 之一，基于它们在 key 总数(即总和)中的“权重”。

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

所以有一个

>>> 68.0/274.0
>>> 0.24817518248175183

24.81% 的百分比更改为选择 A。

您将如何编写处理此问题的算法？换句话说，这确保在 10.000 次随机选择中，A 将被选择 2.481 次？

Answer 1

这是一个加权选择函数，带有一些对其进行练习的代码。

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()