PHP如何按权重随机选择数字

Question

假设我想随机从1-10中选择一个数字，但是每个数字都有不同的权重。

1 - 15% chance
2 - 15% chance
3 - 12% chance
4 - 12% chance
5 - 10% chance
6 - 10% chance
7 - 8% chance
8 - 8% chance
9 - 5% chance
10 - 5% chance

我应该如何用 PHP 编写这个代码？

- Justin

---

你可以使用一个均值为1的标准分布（高斯）算法，但ChristopheD的答案更简单。 - FThompson

Answer 1

我假设你的百分比总和为100%？

用以下方式构建一个数组

15 times a '1' value, 
15 times a '2' value, 
... 
10 times a '6' value, 
8 times a '7' value,
...
5 times 1 '10' value

你最终会得到一个包含100个元素的单一数组。

随机选择一个元素（并从数组中弹出它）。

- ChristopheD

---

有没有一种数学方法可以在没有数组开销的情况下完成这个任务？如果我们要编写一个从1到100,000的程序，应该怎么做呢？ - Justin

制作这样的数组似乎过度了，而且它不支持像10.5％这样的权重。 - Yamiko

@yamikoWebs：如果您需要称重的分辨率为0.5％而不是1％，那么您只需要一个由200个元素组成的数组;-) 对我来说，这看起来像是对手头问题的一个好（简单）解决方案，在我看来，我肯定不会声称这是针对此主题的每种可能变化的绝对解决方案... - ChristopheD

@ChristopheD 我不喜欢创建一个这么大的数组，如果没有必要的话。顺便说一下，我添加了一个类，我认为它更有效率/可维护，作为答案...它一直在底部，因为我一直在编辑它以改进...计划更新它，使其能够通过使用多维数组返回除字符串和整数之外的值，但今天不会:P - Yamiko

数组解法允许您在O(1)的时间复杂度下选择随机元素，但需要O(N)的空间。您也可以做相反的妥协，只需存储一份包含选择项和权重的列表，并通过迭代获取正确的选择（这是Mala的解决方案）。这两种方法都有重要的缺点。您正在寻找的解决方案被称为“别名方法”。这个问题在StackOverflow上已经被多次讨论过。如果您感兴趣，Google上有一个Python实现的例子。 - Jérémie

Answer 2

如果您的权重以百分比表示，那么请在0到100之间选择一个随机数，然后迭代地减去这些百分比，直到您穿过零点：

<?php
function getWeightedRandom() {
    $weights = array(15, 15, 12, ...); // these should add up to 100
    $r = rand(0, 99);
    for ($i=0; $i<count($weights); $i++) {
        $r -= $weights[$i];
        if ($r < 0)
            return $i+1;
    }
}
?>

这还有一个额外的好处，就是支持非整数权重。

- Mala

---

如果值具有相同的权重，则无法工作，将$ weights想象为一个10乘10的数组。您始终会得到第一个值。还取决于$weights是否已排序（降序）。 - ccKep

实际上，它可以使用等权值进行工作，$weights 不需要排序（范围 [0-0.2] 和范围 [0.8-1] 的可能性完全相同）... - Mala

是的，但你在遇到第一个满足 $r <0$ 的值时就返回了。想象一下 $weights = array(1, 90, 9);。你的循环从第一个元素“1”开始迭代，并且仅有2%的概率不返回。（$r=0$ 或$r=1$）（例如，在这个例子中，98% 的时间你会得到那个1% 概率的键）。 - ccKep

你说得没错，这个函数有一小部分的概率不会返回（尽管当$r$为100时，这个概率略低于1%），但你错在它返回的元素概率是正确的。我鼓励你用自己的例子试一下这段代码。将$r$更改为0到99之间（共有100种可能性）可以解决函数偶尔不返回的问题。 - Mala

Answer 3

一个使用以下类的示例，回显带有 OPs 权重的值：

echo 1+Rand::get_weighted_rand(array(15,15,12,12,10,10,8,8,5,5));

以及该类：

class Rand
{
    /*
     * generates a random value based on weight
     * @RETURN MIXED: returns the key of an array element
     * @PARAM $a ARRAY:
     *  the array key is the value returned and the array value is the weight
     *      if the values sum up to less than 100 than the last element of the array 
     *      is the default value when the number is out of the range of other values
     * @PARAM $p INT: number of digits after decimal
     *
     * i.e array(1=>20, 'foo'=>80): has an 80 chance of returning Foo
     * i.e array('bar'=>0.5, 2=>1, 'default'=>0), 1: 98.5% chance of returning default
     */
    public static function get_weighted_rand($a, $p=0)
    {
        if(array_sum($a)>100)
            return FALSE;#total must be less than 100
        $p=pow(10, $p+2);
        $n=mt_rand(1,$p)*(100/$p);
        $range=100;
        foreach($a as $k=>$v)
        {
            $range-=$v;
            if($n>$range)
                return $k;
        }
            #returning default value
        end($a);
        return key($a);
    }
}

- Yamiko

Answer 4

把它们都放到数组里多次，例如1放15次，3放12次等等。然后从该数组中随机选择一个数字。

$array = array_merge (array_fill (0, 15, 1), array_fill (0, 15, 2), array_fill (0, 12, 3), array_fill (0, 12, 4), array_fill (0, 10, 5), array_fill (0, 10, 6), array_fill (0, 8, 7), array_fill (0, 8, 8), array_fill (0, 5, 9), array_fill (0, 5, 10));
$random_number = array_rand ($array);

- Jeroen