Generating a random sequence with no repeats

Question

Hi,

I read a couple of posts here about generating random sequence without repeats (for example http://stackoverflow.com/questions/693880/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

Unless you have good reasons to, you don't want to reinvent pseudo random generation. It is quite possible to get something wrong. I'd suggest starting with an array with A[i]=i

then do this:

for (i=0; i< n; i++) {
  j = random_number_between(i,n-1);
  swap(A[i],A[j]);
}

Edit This is in response to the comments below:

How random do you want the sequence to be. Note that the inherent information in a randomly chosen permutation is log(n!) which is somewhere close to n/e bits. So you do need that many random bits to be generated. Now since you want these many random bits stored anywhere I think (more like a gut feeling than a mathematical proof) it would be hard to do a truly random permutation without that much storage).

But if you just want a sequence that is not easy to reverse engineer you could just concatenate a number of 1:1 functions one after the other. Two things come to mind: - keep a counter i for the sequence that goes from 0 through N-1.

• do log_2(N/2) bit flips on i where bits to flip are chosen at random when when you are starting the sequence.

• generate a random permutation over log_2(N) bits at the beginning of sequence using the above method and then swap the bits in the result above.

• Find a random number r1 that is a relative prime to n at and another random number r2 between 0 and n-1. Your i-th number is = r2^r % n.

Some combination of these should give you a hard to reverse engineer sequence. The key is that the more random bits you infuse the harder it is to reverse engineer.

One thing that comes to mind is that if your range is 0..N-1, just find a large number P that is a relative prime to N and choose another random number