generics - 根据概率随机选择获奖者

想象一下，您有一系列代表竞争对手的哈希值以及它们赢得奖金的概率(0到1之间的 float )。喜欢:

  [ {:name => "Adam" , :prob => 0.5}
    {:name => "Ben" , :prob => 1.0}
    {:name => "Chris" , :prob => 0.1}
    {:name => "Daniel" , :prob => 0.2}
    {:name => "Ed" , :prob => 0.7}
    {:name => "Frey" , :prob => 0.5}
    {:name => "Gilbert" , :prob => 0.3}
  ]

我希望有一种算法，我可以使用随机数选择三个获奖者，但要尊重每个人的概率。

样本的总概率为3.3

逻辑方法是计算随机值，例如:

val = rand(33)/10.0

并扫描阵列，直到找到达到随机数的人。

这种方法有效，但是它意味着对阵列进行扫描。

我想知道是否会有更直接的解决方案。有任何想法吗？

PS:想象一下数组中可能有很多元素。

最佳答案

我在想这个，我的结果很有意义:

根据概率对 vector 排序:[a = 0.1，b = 0.2，c = 0.3，d = 0.4]

选择一个随机数(例如0.5)

从头开始迭代，对概率值求和，并在概率值较高时停止:
答案= 0.1 + 0.2 + 0.3。因此，0.6> 0.5，我们将值'c'设为

我的主旨是， vector 结尾处的值应具有较高的被选择概率。我已经在python中实现了:

values = [0.1,0.2,0.3,0.4]
count_values = len(values)*[0]
answer = len(values)*[0]

iterations = 10000

for i in range(0,iterations):
    rand = float(random.randint(0,iterations))/iterations
    count = 0
    sum = 0
    while sum <= rand and count <= len(values):
        sum += values[count]
        count += 1
    count_values[count-1]+=1

for i in range(0,len(count_values)):
    answer[i] = float(count_values[i])/iterations

然后运行几次，我计算出所有元素被选择的概率应与我们的初始概率相符:

[0.1043, 0.196, 0.307, 0.3927]
[0.1018, 0.2003, 0.2954, 0.4025]
[0.0965, 0.1997, 0.3039, 0.3999]

关于generics - 根据概率随机选择获奖者，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9072904/