如何确保随机数是唯一的而不是重复的？ [英] How to be sure that random numbers are unique and not duplicated?

问题描述

我有一个生成随机数的简单代码

I have a simple code which generates random numbers

SecureRandom random = new SecureRandom();
...
public int getRandomNumber(int maxValue) {
    return random.nextInt(maxValue);
}

上述方法大约调用10次（不在循环中）。我想确保所有数字都是唯一的（假设 maxValue> 1000 ）。

The method above is called about 10 times (not in a loop). I want to ensure that all the numbers are unique (assuming that maxValue > 1000).

我可以吗？我确定每次打电话都会得到唯一的号码吗？如果没有，我该如何解决？

Can I be sure that I will get unique numbers every time I call it? If not, how can I fix it?

编辑：我可能已经模糊地说过了。我想避免手动检查，如果我真的有唯一的数字，所以我想知道是否有更好的解决方案。

I may have said it vaguely. I wanted to avoid manual checks if I really got unique numbers so I was wondering if there is a better solution.

推荐答案

有实现这一目标的不同方式更合适将取决于您需要从多少数字中选择多少数字。

There are different ways of achieving this and which is more appropriate will depend on how many numbers you need to pick from how many.

• 如果您选择来自大量潜在数字的少量随机数，那么你最好只是将先前选择的数字存储在一个集合中并手动检查重复数据。大多数情况下，您实际上不会获得重复，并且实际上测试的成本几乎为零。它可能听起来不那么优雅，但它实际上并不像听起来那么糟糕。


• 一些基础随机数生成算法不会在原始级别产生重复。例如，一个名为 XORShift 生成器的算法可以有效地生成所有数字在一定范围内，洗牌没有重复。所以你基本上在序列中选择一个随机的起始点然后只生成下面的n个数字，你知道不会有重复。但在这种情况下你不能随意选择max：它必须是有问题的发电机的自然最大值。



• 如果可能的数字范围很小 - 是的，但是您需要选择的数字的数量在该范围的几个数量级内，那么您可以将其视为随机选择问题。例如，要在10,000,000范围内选择100,000个不重复的数字，我可以这样做：

• If you are selecting a small number of random numbers from a large range of potential numbers, then you're probably best just storing previously chosen numbers in a set and "manually" checking for duplicates. Most of the time, you won't actually get a duplicate and the test will have practically zero cost in practical terms. It might sound inelegant, but it's not actually as bad as it sounds.
• Some underlying random number generation algorithms don't produce duplicates at their "raw" level. So for example, an algorithm called a XORShift generator can effectively produce all of the numbers within a certain range, shuffled without duplicates. So you basically choose a random starting point in the sequence then just generate the next n numbers and you know there won't be duplicates. But you can't arbitrarily choose "max" in this case: it has to be the natural maximum of the generator in question.

• If the range of possible numbers is small-ish but the number of numbers you need to pick is within a couple of orders of magnitude of that range, then you could treat this as a random selection problem. For example, to choose 100,000 numbers within the range 10,000,000 without duplicates, I can do this:

设m是随机数的数量I到目前为止已经选择了

Let m be the number of random numbers I've chosen so far

对于i = 1到10,000,000

For i = 1 to 10,000,000

生成一个随机（浮点）数，r，在0-1范围内

Generate a random (floating point) number, r, in the range 0-1

如果（r <（100,000-m）/（10,000,000-i）），则添加我到列表并增加m

If (r < (100,000-m)/(10,000,000-i)), then add i to the list and increment m

随机播放列表，然后根据需要从列表中依次选择数字

Shuffle the list, then pick numbers sequentially from the list as required

但很明显，如果你需要选择一个相当大比例的选项，选择后一个选项只有很多意义整体数字范围。为了选择1到10亿范围内的10个数字，你将产生10亿个随机数，当你只是检查重复数据时，你实际上不太可能得到重复，并且最终只会生成10个随机数数字。

But obviously, there's only much point in choosing the latter option if you need to pick some reasonably large proportion of the overall range of numbers. For choosing 10 numbers in the range 1 to a billion, you would be generating a billion random numbers when by just checking for duplicates as you go, you'd be very unlikely to actually get a duplicate and would only have ended up generating 10 random numbers.

这篇关于如何确保随机数是唯一的而不是重复的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！