How to be sure that random numbers are unique and

问题:

I have a simple code which generates random numbers

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

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?

EDIT: 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.

回答1:

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.

• 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:

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

  For i = 1 to 10,000,000

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

  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

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.

回答2:

A random sequence does not mean that all values are unique. The sequence 1,1,1,1 is exactly as likely as the sequence 712,4,22,424.

In other words, if you want to be guaranteed a sequence of unique numbers, generate 10 of them at once, check for the uniqueness condition of your choice and store them, then pick a number from that list instead of generating a random number in your 10 places.

回答3:

Every time you call Random#nextInt(int) you will get

a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive).

If you want x unique numbers, keep getting new numbers until you have that many, then select your "random" number from that list. However, since you are filtering the numbers generated, they won't truly be random anymore.

回答4:

For such a small number of possible values, a trivial implementation would be to put your 1000 integers in a list, and have a loop which, at each iteration, generates a random number between 0 and list.size(), pick the number stored at this index, and remove it from the list.

回答5:

This is code is very efficient with the CPU at the cost of memory. Each potiental value cost sizeof(int) * maxValue. An unsigned integer will work up to 65535 as a max. long can be used at the cost of a lot of memory 2000 bytes for 1000 values of 16 bit integers.

The whole purpose of the array is to say have you used this value before or not 1 = yes 'anything else = no 'The while loop will keep generating random numbers until a unique value is found. 'after a good random value is found it marks it as used and then returns it. 'Be careful of the scope of variable a as if it goes out of scope your array could erased. ' I have used this in c and it works. ' may take a bit of brushing up to get it working in Java.

unsigned int a(1000);

public int getRandomNumber(int maxValue) {
  unsigned int rand;

  while(a(rand)==1) {
    rand=random.nextInt(maxValue);
    if (a(rand)!=1) { a(rand)=1; return rand;}
  }

}