Generate random integers in java_问答_开发者_运维开发者技术经验分享

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

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.

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

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.)

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.

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.

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.

Since I can't comment on the earlier answers above due to not having enough reputation (which seems backwards... shouldn't I be able to comment on others' answers, but not provide my own answers?... anyway...), I'd like to mention that there is a major flaw with relying on Collections.shuffle() which has little to do with the memory constraints of your collection:

Collections.shuffle() uses a Random object, which in Java uses a 48-bit seed. This means there are 281,474,976,710,656 possible seed values. That seems like a lot. But consider if you want to use this method to shuffle a 52-card deck. A 52-card deck has 52! (over 8*10^67 possible configurations). Since you'll always get the same shuffled results if you use the same seed, you can see that the possible configurations of a 52-card deck that Collections.shuffle() can produce is but a small fraction of all the possible configurations.

In fact, Collections.shuffle() is not a good solution for shuffling any collection over 16 elements. A 17-element collection has 17! or 355,687,428,096,000 configurations, meaning 74,212,451,385,344 configurations will never be the outcome of Collections.shuffle() for a 17-element list.

Depending on your needs, this can be extremely important. Poor choice of shuffle/randomization techniques can leave your software vulnerable to attack. For instance, if you used Collections.shuffle() or a similar algorithm to implement a commercial poker server, your shuffling would be biased and a savvy computer-assisted player could use that knowledge to their benefit, as it skews the odds.

If you want 256 random numbers between 0 and 255, generate one random byte, then XOR a counter with it.

byte randomSeed = rng.nextInt(255);
for (int i = 0; i < 256; i++) {
    byte randomResult = randomSeed ^ (byte) i;
    << Do something with randomResult >>
}

Works for any power of 2.

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.

Linear Congruential Generator can be used to generate a cycle with different random numbers (full cycle).