按比例返回数组中的随机值

Question

I have an array like

$keywords = array('apple'=>10,'orange'=>2,'grape'=>12); 

我想随机从数组中选择一个“键”。但是，选取元素的概率分布应该与其值成比例。

- Eastern Monk

Answer 1

将所有值相加（10+2+12等于24）；在范围[0, 24)内获取一个随机数，并根据随机数是否位于[0, 10)，[10, 12)或[12, 24)中选择相应的元素。

- Kerrek SB

---

这是我所做的。一个愚蠢的方法可能是创建一个包含10次“apple”、“orange” 2次等元素的数组，然后使用array_rand随机选择一个元素。 - Eastern Monk

哈哈，没错。数学上是一样的，但关键是以最高效的方式编程 :-) - Kerrek SB

如果你要选择许多随机值，那么Akshar的算法更有效率。Akshar的时间复杂度为O(1)，而Kerrek的时间复杂度为O(log(n))。 - Jyaif

这是一个实现的链接：https://dev59.com/ibjna4cB1Zd3GeqP2wJZ#59268654 - Guntram

Answer 2

我会这样做：

    $probabilities = array('apple'=>50, 'orange'=>20, 'banana'=>10);

    function random_probability($probabilities) {
      $rand = rand(0, array_sum($probabilities));
      do {
        $sum = array_sum($probabilities);
        if($rand <= $sum && $rand >= $sum - end($probabilities)) {
          return key($probabilities);
        }
      } while(array_pop($probabilities));
    }

- Peter Briers

Answer 3

一种O(log(n))的方法（直接从非常相似问题的答案中摘取）：

通常的技巧是将数组转换为累加和数组：

 [10 60 5 25]  --> [10 70 75 100]

从零到累计总数（在本例中：0 <= x < 100）中随机选择一个数字。然后，在累积数组上使用bisection查找索引，以定位原始数组中的元素。

Random variable x      Index in the Cumulative Array      Value in Original Array
-----------------      -----------------------------      ----------------------
 0 <= x < 10                      0                            10
10 <= x < 70                      1                            60
70 <= x < 75                      2                             5
75 <= x < 100                     3                            25 

例如，如果随机变量x为4，则将累积数组二分后得到的位置索引为0，对应于原始数组中的10。

而如果随机变量x为72，则将累积数组二分后得到的位置索引为2，对应于原始数组中的5。

- Oliver Coleman