Generate random integers in java

Question

How to generate random integers but making sure that they don't ever repeat?

For now I use :

Random randomGenerator = new Random();
randomGenerator.nextInt(100);

EDIT I

I'm looking for most efficient way, or least bad

EDIT II

Range is not important

Answer 1

ArrayList<Integer> list = new ArrayList<Integer>(100);
for(int i = 0; i < 100; i++)
{
  list.add(i);
}
Collections.shuffle(list);

Now, list contains the numbers 0 through 99, but in a random order.

Answer 2

If you have a very large range of integers (>>100), then you could put the generated integers into a hash table. When generating new random numbers, keep generating until you get a number which isn't in your hash table.

Answer 3

Matthew Flaschen has the solution that will work for small numbers. If your range is really big, it could be better to keep track of used numbers using some sort of Set:

Set usedNumbers = new HashSet();
Random randomGenerator = new Random();
int currentNumber;
while(IStillWantMoreNumbers) {
    do {
        currentNumber = randomGenerator.nextInt(100000);
    } while (usedNumbers.contains(currentNumber));
}

You'll have to be careful with this though, because as the proportion of "used" numbers increases, the amount of time this function takes will increase exponentially. It's really only a good idea if your range is much larger than the amount of numbers you need to generate.

Answer 4

If the Range of values is not finite, then you can create an object which uses a List to keep track of the Ranges of used Integers. Each time a new random integer is needed, one would be generated and checked against the used ranges. If the integer is unused, then it would add that integer as a new used Range, add it to an existing used Range, or merge two Ranges as appropriate.

But you probably really want Matthew Flaschen's solution.

Answer 5

Depending on the application, you could also generate a strictly increasing sequence, i.e. start with a seed and add a random number within a range to it, then re-use that result as the seed for the next number. You can set how guessable it is by adjusting the range, balancing this with how many numbers you will need (if you made incremental steps of up to e.g., 1,000, you're not going to exhaust a 64-bit unsigned integer very quickly, for example).

Of course, this is pretty bad if you're trying to create some kind of unguessable number in the cryptographic sense, however having a non-repeating sequence would probably provide a reasonably effective attack on any cypher based on it, so I'm hoping you're not employing this in any kind of security context.

That said, this solution is not prone to timing attacks, which some of the others suggested are.

Answer 6

How to generate random integers but making sure that they don't ever repeat?

First, I'd just like to point out that the constraint that the numbers don't repeat makes them non-random by definition.

I think that what you really need is a randomly generated permutation of the numbers in some range; e.g. 0 to 99. Even then, once you have used all numbers in the range, a repeat is unavoidable.

Obviously, you can increase the size of your range so that you can get a larger number without any repeats. But when you do this you run into the problem that your generator needs to remember all previously generated numbers. For large N that takes a lot of memory.

The alternative to remembering lots of numbers is to use a pseudo-random number generator with a long cycle length, and return the entire state of the generator as the "random" number. That guarantees no repeated numbers ... until the generator cycles.

(This answer is probably way beyond what the OP is interested in ... but someone might find it useful.)

Answer 7

If what you want is a pseudo-random non-repeating sequence of numbers then you should look at a linear feedback shift register. It will produce all the numbers between 0 and a given power of 2 without ever repeating. You can easily limit it to N by picking the nearest larger power of 2 and discarding all results over N. It doesn't have the memory constraints the other colleciton based solutions here have.

You can find java implementations here