StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POGenerating a random sequence with no repeats
text
Body
copied!<p>I read a couple of posts here about generating random sequence without repeats (for example <a href="https://stackoverflow.com/questions/693880/create-random-number-sequence-with-no-repeats">Create Random Number Sequence with No Repeats</a>) and decided to implement it for my own need</p> <p>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.</p> <p>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:</p> <ul> <li>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</li> <li>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.</li> <li>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</li> </ul> <p>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.</p> <p>Thanks</p> <p>Max</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload