一个由mt_rand()生成的五位数数字有多独特？

Question

一个由mt_rand()生成的五位数数字有多独特？

4

我想知道，如果你用mt_rand()函数生成一个5位数的随机数字，这个数字有多独特？在这个例子中，我尝试使用这个函数获取500个随机数，并且其中一些是重复的。 http://www.php.net/manual/en/function.mt-rand.php

<?php
header('Content-Type: text/plain');

$errors = array();
$uniques = array();
for($i = 0; $i < 500; ++$i)
{
    $random_code = mt_rand(10000, 99999);
    if(!in_array($random_code, $uniques))
    {
        $uniques[] = $random_code;
    }
    else
    {
        $errors[] = $random_code;
    }
}

/**
 * If you get any data in this array, it is not exactly unique
 * Run this script for few times and you may see some repeats
 */
print_r($errors);
?>

为了确保在循环中抽取的前500个随机数是唯一的，可能需要多少位数字？

- Bimal Poudel

一个随机数并不能保证是“唯一”的。 - Jared Farrish

1

请查看《生日问题》（http://en.wikipedia.org/wiki/Birthday_problem）了解该问题背后的数学知识。 - user2864740

随机不等于唯一。如果您说明数字的用途，您可能会得到更有用的答案。 - Sverri M. Olsen

4个回答

5

为什么不使用 range、shuffle 和 slice 呢？

<?php

$uniques = range(10000, 99999);
shuffle($uniques);
$uniques = array_slice($uniques, 0, 500);

print_r($uniques);

Output:

Array
(
    [0] => 91652
    [1] => 87559
    [2] => 68494
    [3] => 70561
    [4] => 16514
    [5] => 71605
    [6] => 96725
    [7] => 15908
    [8] => 14923
    [9] => 10752
    [10] => 13816
    *** truncated ***
)

这种方法的成本较低，因为它不会每次搜索数组以查看项目是否已添加。尽管如此，这确实使得这种方法不太“随机”。应提供更多信息，说明这些数字将在哪里使用。如果这是一个在线赌博网站，那就太糟糕了！但是，如果用于返回占星网站的“幸运”数字，我认为这将是可以接受的。

此外，该方法可以扩展，将洗牌方法更改为使用mt_rand（原始方法仅使用rand）。也可以使用openssl_random_pseudo_bytes，但可能有些过度。

- Dave Chen

1

@ShankarDamodaran 我没有在这里投票，但是这个答案不好，它是错误的。它没有回答问题。Josh的答案是正确的。 - hek2mgl

1

@hek2mgl，我同意你的看法，这个答案并没有提及mt_rand()函数的“独特性”。这只是解决问题的另一种方式。 - Shankar Narayana Damodaran

1

@MarcAudet - 你需要在其他地方了解随机性和适用性是如何确定的（我不是专家），但让我怀疑的一件事是适合度；每个条目必须在每次洗牌中仅适合一次（并且必须被表示），这意味着每个数字都被表示。与OP的愿望相反，这减少了“随机性”，因为重复项是真正随机的，而群体中的适应性则没有被表示。这可能等同于另一个答案（我没有数学技能来推测），但我猜它更糟。 - Jared Farrish

1

这个方法是我认为比较合适的方式，除非问题提供了进一步的信息（例如这些数字将在哪里使用，例如在线赌博、随机帖子选择等）。持续搜索一个大小达到500个元素的数组是昂贵的，因此它高度取决于这些数字需要多么随机。如果您需要它们更加随机，我认为可以实现洗牌的另一种实现。 - Dave Chen

1

我看选择方法的一个重要因素是你所需的值的数量n。如果n=3，那么这种方法就过于复杂了，我认为性能和随机性很重要，因此选择了mt_rand()而不是rand()。如果你有n=89999，那么使用do{}while()来选择新数字的解决方案将运行得非常缓慢。n=500似乎太低了，无法理解为什么要使用shuffle(range())。 - Josh from Qaribou

显示剩余9条评论

3

生日悖论在这里发挥作用。如果你从10000-99999中随机选择500次，有很大的可能会出现重复。

小数字的直观想法

如果你抛两次硬币，你有一半的概率得到一样的结果。如果你掷一个六面骰子两次，你有1/6的概率得到一样的结果。如果你掷3次，你有4/9（44%）的概率得到一样的结果。如果你掷4次，你至少有13/18（63.33%）的概率得到一样的结果。掷第五次，概率是49/54（90.7%）。掷第六次，概率是98.5%。掷第七次，概率是100%。

如果你用20面骰子代替六面骰子，概率增长得比较慢，但是它们确实增长了。掷3次，你有14.5%的概率得到一样的结果。掷6次，概率是69.5%。掷10次，概率是96.7%，几乎可以肯定。

数学计算

我们定义一个函数f(num_rolls, num_sides)，将其推广到任何数量的掷骰子方法，以及任何有限的选择集。我们将f(num_rolls, num_sides)定义为在num_rolls次掷出一个num_sides-面骰子时不重复的概率。

现在我们可以尝试建立一个递归定义。要获得num_rolls个唯一数字，你需要首先掷num_rolls-1个唯一数字，然后掷一个更多的唯一数字，现在已经取了num_rolls-1个数字。因此，

f(num_rolls, num_sides) = 
  f(num_rolls-1, num_sides) * (num_sides - (num_rolls - 1)) / num_sides

此外，

f(num_rolls + 1, num_side) = 
  f(num_rolls, num_sides) * (num_sides - num_rolls) / num_sides

这个函数遵循逻辑衰减曲线，从1开始缓慢移动（由于 num_rolls 非常低，每步的变化非常小），然后随着 num_rolls 的增加而逐渐加速，最终在函数值越来越接近0时逐渐减弱。

我创建了一个谷歌文档电子表格，其中内置此函数作为公式，以便您在此处进行操作：https://docs.google.com/spreadsheets/d/1bNJ5RFBsXrBr_1BEXgWGein4iXtobsNjw9dCCVeI2_8

将其与您的特定问题联系起来

您已经掷了一个90000面骰子500次。上面的电子表格显示，如果假设完全随机的mt_rand，您至少会有75%的几率出现至少一对重复数字。从数学上讲，您的代码执行的操作是从一个带有替换的集合中选择N个元素。换句话说，您从90000个物品的袋子中随机选择一个数字，写下来，然后将其放回袋子中，再选择另一个随机数字，重复500次。听起来您想要所有的数字都是不同的，换句话说，您想要从一个不带替换的集合中选择N个元素。有一些算法可以实现这一点。Dave Chen的建议是洗牌然后切片，这是一个相对简单的方法。Qaribou的Josh的建议是分别拒绝重复项。

- Yuliy

1

您的问题涉及到“生日悖论”的变体，即如果一个班级有N个学生，至少有两个学生生日相同的概率是多少？请参见Wikipedia：生日悖论。

您可以轻松修改在那里显示的公式来回答您的问题。每个学生的生日有365个等可能的可能性，而您有90001（=99999-10000+2）个等可能的整数可以在10000和99999之间生成。如果您生成500个这样的数字，则至少有两个数字相同的概率为：

P(500)= 1- 90001! / ( 90001^n (90001 - 500)! ) = 0.75

因此，您生成的500个数字中至少有两个数字相同的概率为75％，换句话说，您使用的方法只有25％的成功率，能够得到500个不同的数字。

正如其他人已经建议的那样，我建议检查您的算法中是否有重复的数字，而不仅仅是盲目地生成随机数字，并希望您不会在任何一对数字之间匹配。

- Samuel W.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Josh from Qaribou · Accepted Answer

如果数字是真正随机的，那么有可能会出现重复的情况。无论数字有多少位数，增加更多的位数可以使重复的概率大大降低，但仍然存在这种可能性。

最好的方法是检查是否存在冲突，然后循环直到没有冲突，像这样：

$uniques = array();
for($i = 0; $i < 500; $i++) {
    do {
        $code = mt_rand(10000, 99999);
    } while(in_array($code, $uniques));
    $uniques[] = $code
}