php - 固定比例选择

Question

我有一组元素，我需要从中选择任何一个元素。每个元素都与一个百分比机会相关联。百分比相加为 100。

我需要从这些元素中选择一个，以便元素被选中的机会等于百分比值。所以如果一个元素有 25% 的机会，它应该有 25% 的机会被选中。换句话说，如果我们选择元素 100 万次，则该元素应该被选择近 25 万次。

Answer 1

您所描述的是一个多项式过程。

http://en.wikipedia.org/wiki/Multinomial_distribution#Sampling_from_a_multinomial_distribution

他们生成这种随机过程的方式是这样的: (我将使用伪代码，但将其转化为真实代码应该很容易。)

1. 按照概率的相反顺序对“框”进行排序: (不需要。这只是一个优化) 这样你就有了例如 values=[0.45,0.3,0.15,0.1]

2. 然后创建“累积”分布，它是索引 <=i 的所有元素的总和。 伪代码:

   cumulant=[0,0,0,0]    // initiate it
   s=0
   for j=0 to size()-1 {
      s=s+values[i] ; 
      cumulant[i]=s
   }
   

   在我们的例子中 cumulant=[0.45,0.70,0.85 ,1 ]

3. 在 0 和 1 之间取一个统一的随机数 x。 对于 PHP:http://php.net/manual/en/function.rand.php

4. 得到的随机框索引i是

   cumulant[i]< x 的最高 i

伪代码:

for j=0 to size()-1 {
  if !(cumulant[i]<){
     print "your index is ",i
     break;
  }

就是这样。回到第 3 点得到另一个随机索引 i。

如果您按照上面的建议排序，这意味着最终搜索会更快。例如，如果你有这个概率向量: 0.001 0.001 0.001 0.001 0.996 然后，当你对它进行排序时，你几乎总是只需要查看索引 i=0，因为随机数 x 几乎总是小于 0.996 .排序是否有效取决于您是否重复使用相同的“盒子”。所以，是的，25 万次尝试会有很大帮助。请记住，您获得的框索引 i 是针对已排序向量的。