JavaScript随机数生成:空间中唯一的500个整数10 ^ 6:发生碰撞

Question

下面是JS中随机整数生成的一个非常简单的例子,我不是通过任何方式"扩展极限".

我只从一个非常大的空间生成500个独特的随机整数,10 ^ 6.

然而,如果你一直点击按钮,你偶尔会看到500中的499或498个独特的.它不会经常发生,但它可能发生在每10或15次点击.这是为什么？我的空间是100万.我不希望在每个第10次或第20次点击频率的500个样本中发生冲突.

要进行测试,请继续单击按钮并观察控制台.

function run() {
  var nums = new Set();

  for (var i = 0; i < 500; i++) {
    nums.add(randomInteger10to6th());
  }

  console.clear();
  console.log('Random 10^6 Unique Integer set: ' + nums.size);
}

function randomInteger10to6th() {
   return Math.round(Math.random() * Math.pow(10,6))
}

<button id="run" onclick="run();">Run 500 Random Integers, Space: 10^6</button>

Answer 1

当您从1-1e6中选择500个随机数时,您看到所有唯一数字的概率可以计算如下:1e6/1e6*999,999/1e6*999,998/1e6*...*999,501/1e6

这大概是0.88

这意味着超过10%的时间,您将在500个随机数的列表中至少有一个副本.

您可以在下面的代码段中验证100次实验中的此行为:

function run() {
  var nums = new Set();
  for (var i = 0; i < 500; i++) {
    nums.add(randomInteger10to6th());
  }
  return nums;
}

function randomInteger10to6th() {
  return Math.round(Math.random() * Math.pow(10, 6))
}

// perform 100 experiments and see how many have duplicates
var uniques = 0, collisions = 0;
for (var i = 0; i < 100; i++) {
  var nums = run();
  if (nums.size === 500) uniques++;
  else collisions++;
}

console.log('Runs that generated unique numbers', uniques);
console.log('Runs that resulted in collisions', collisions);