generics - 根据概率选择获胜者的随机数

Question

假设您有一个哈希值数组，表示竞争对手及其中奖概率(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:想象一下数组可能有大量元素。

Answer 1

创建一个循环，直到选出 3 名获胜者。在这个循环中，使用您选择的编程语言中可用的任何随机方法生成一个特定的随机数。在此之后，开始遍历用户。如果任何用户的概率小于此随机数，则接受该用户为赢家。如果在循环的任何迭代中都没有选择获胜者，例如，在列表中的最低概率为 0.2 且生成的随机数为 0.1 的情况下，在这种情况下，继续循环的下一次迭代。当您获得 3 个获胜者时，就可以打破循环。一个可能的伪代码如下:

int count=0;
while(count<3){
    temp=GenerateRandomNumber()
    int userIndex= AcceptWinner(UserListProbability,temp)
    //here keep iterating through the users to check which user's probability is less than temp and returns the index of the winner in the List

    if(userIndex==-1)//No winner selected
        continue;
    else{
        count++;
        Print List(userIndex)
    }
}

注意:列表要排序