(Python)算法根据比例/权重随机选择一个键

Question

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

假设我有一个字典k:

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

我现在想要根据它们在总(即总和)数量上的"权重"随机选择其中一个键.

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

所以有一个

>>> 68.0/274.0
>>> 0.24817518248175183

选择A的变化率为24.81%.

你会如何编写一个能够解决这个问题的算法？换句话说,这确保在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()

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

算法将是这样的..

在 1 到 274 之间随机选择一个数字。为此，请调用 rand() 函数（假设它返回 0 到 1 之间的值），将 rand() 乘以 274。结果值现在应该在一个范围内。如果在 1 到 68 之间，则选择 A，如果在 69 到 130 之间，则选择 B，依此类推。这样，您的概率就会保持不变，并且您的操作会成功。

PS：我是Java人，不懂Python的语法。