JavaScript随机数生成:空间中唯一的500个整数10^6:获取冲突

Question

下面是JS中随机整数生成的一个非常简单的例子，我不会以任何方式"拉伸极限"。

我只是从一个很大的空间生成500个唯一的随机整数，10^6。

然而，如果你一直点击按钮，你偶尔会看到500个中有499或498个独特的。这种情况并不经常发生，但可能每点击10次或15次就会发生。为什么？我的空间是100万。我不希望在500个样本中出现每10次或20次点击频率的碰撞。

要进行测试，请继续单击按钮并观看控制台。

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*999999/1e6*9999 8/1e6*…*999501/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);

Answer 2

"随机"的意思是：它是随机的。该范围中的每个值都有相同的被选择概率，无论之前选择了什么。因此，即使它选择了数字5，例如，它仍然有同样的机会再次选择5，就像它选择任何其他数字一样。你不应该指望随机数可以避免重复——如果是这样，它们就不会是随机的：(

Answer 3

由于您从大样本中生成的随机数相对较少，因此您应该能够在碰撞时重新生成一个新的数字。添加随机数字直到达到500将导致对随机生成器的一些额外调用，但它将保证500个唯一数字：

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

while (nums.size < 500){
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 4

您也可以使用简单的数组来代替Set()。首先，创建500个索引的数组，然后填充它

function run() {
/* first create an array with 500 slots, then fill it with 
undefined ( fill() without args is undefined ). For the 
last step map through 500 slots of undefined and overwrite 
it with a random number */
return new Array(500).fill().map(x => Math.round(Math.random() * Math.pow(10,6)))
}
console.log(run().length)

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

如果你想删除重复项，那么你可以简单地过滤掉它们并重新计算。

function run() {
// same like the upper function but with a duplicates filter
let arrayWithNumbers = new Array(500).fill().map(x => Math.round(Math.random() * Math.pow(10,6))).filter((item, idx, self) => self.indexOf(item) == idx)
// run again if array less than 500
if(arrayWithNumbers.length !== 500) { 
run() 
}
return arrayWithNumbers
}
console.log(run().length)

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