根据概率随机选择获奖者 [英] Random number to select winners based on probability

问题描述

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

Imagine you have an array of hashes representing competitor and their probability to win the prize (a float between 0 and 1). Like:

  [ {: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}
  ]

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

I would like to have an algorithm on which I can select three winners using random numbers but respecting the probability of each person.

样本的总概率为3.3

The total probability of the sample is 3.3

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

A logical approach would be to calculate the random value like:

val = rand(33)/10.0

然后扫描数组，直到找到达到随机数的人为止.

And scan the array until I get the person which reaches the random number.

这种方法有效，但是它意味着对数组进行扫描.

This approach works but it implies a scan in the array.

我想知道是否会有更直接的解决方案.有什么想法吗?

I wonder if there would be a more straightforward solution. Any ideas?

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

PS: Imagine the array might have a great amount of elements.

推荐答案

我正在考虑这一点，我认为我的结果很有意义:

I was thinking about this and I think my result makes sense:

1. 根据概率对向量进行排序:[a = 0.1，b = 0.2，c = 0.3，d = 0.4]
2. 选择一个随机数(例如0.5)
3. 从头开始迭代，对概率值求和，并在概率值较高时停止: 答案= 0.1 + 0.2 + 0.3.因此，0.6> 0.5，我们将值定为'c'

1. sort the vector according to the probability: [a=0.1,b=0.2,c=0.3,d=0.4]
2. choose a random number (e.g. 0.5)
3. iterate from the beginning and sum the probability values and stop when it is higher: answer = 0.1 + 0.2 + 0.3. So, 0.6 > 0.5, we value 'c'

我的要点是，向量结尾处的值应具有较高的被选择概率.我已经在python中实现了:

my gist over this is that the values in the end of the vector should have a higher probability of being chosen. I have implemented in 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

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

and running several times, I calculated the probability of all elements being chosen, that should match our initial probability:

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

这篇关于根据概率随机选择获奖者的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！