Generating a random sequence with no repeats

Question

I read a couple of posts here about generating random sequence without repeats (for example Create Random Number Sequence with No Repeats) and decided to implement it for my own need

Actually it was an algorithm applying some non-destructive (reversible) operations with the bits of the current counter in order to get a pseudo-random number that should appear only once. Since the operations are reversible, different source numbers will give different result numbers.

There are at least several operation possible like exchange two bits, invert a bit, cyclic shift. If we use only ones mentioned, the quality of the sequence won't be great since the nearby counter will produce results with similar number of zeros and ones. The real game changer was xor one bit by another bit. Now the sequences looks much better, but the questions are:

• Is there smallest subset of the operations that will be enough (for example invert bit + xor bit by another bit) and adding any other just will make the algorithm harder to read while giving no extra benefits
• How can I approximately guess the number of operations for a given range in order for the sequence to be good enough. For example 200 operations for numbers from 0 to 31 gives visually good results, but 200 operations for the range 0..199 sometimes gives blocks of close numbers.
• Is there an algorithm or a test suite for testing such sequences. I'm aware and used once the suites that can test general random sequences, but this one is a different so probably some special suite needed or at least some conversion back to the general random world

UPDATE: As I posted in the comment here, there's already a generator like this: AES Encryption, but unfortunately it can only be used for 128-bit ranges.

Thanks

Max

Answer 1

Problem:

Generate a list of unique random integers between 1 and N.

Solution:

1. Generate N random numbers; Gaussian or uniform ...
2. Sort them; save the index (ie, the location of each value in the list)
3. The index of the sort is your list.

In Matlab:

z = rand( [N 1] );
[dummy iz] = sort(z);

% iz is your list.