# Are all pseudo randomly generated numbers within a given period unique?

This will of course depend on the algorithm generating the pseudo random numbers, but what I'm wondering is whether practical, usable pseudo-random number generating algorithms exist that never repeat the same number twice until their period is up.

• I highly doubt that this would be a desirable property or one that was designed - as it makes the end of the sequence highly predictable. Some PRNGs may have this as an unintended consequence, but I really doubt it. Commented Mar 23, 2018 at 16:01
• A sequence of "random" numbers that never repeats a number until all numbers are used up isn't really random, is it? The desired quality of a good PRNG is even distribution across the desired numeric range, not using all of the numbers only once. Commented Mar 23, 2018 at 16:03
• A coinflip on such a generator would mean that even best case, 50% of flips are 100% predictable. Not very random. Commented Mar 23, 2018 at 16:17
• Maybe check out shuffling algorithms. Start with a set of unique numbers then shuffle them into a random order. Commented Mar 23, 2018 at 16:20
• @KChaloux Right was just going to say that would appear to be the answer for a practical, usable algorithm that never repeats the same number twice. Commented Mar 23, 2018 at 16:22

As the accepted answer correctly notes, that would be a horrible PRNG. You want the period of the generator to be many orders of magnitude larger than the number of values it generates; your proposal is that they be equal.

But your question was not "critique this idea" but rather

does a practical, usable pseudo-random number generating algorithms exist that never repeat the same number twice until their period is up.

Sure, that's easy. Here's one:

• Choose the period you want. Call it `p`.
• Plainly the number of values that the PRNG generates must be not less than `p`, because otherwise by the pigeonhole principle, it repeats an output in fewer than `p` steps. Let's suppose that the number of possible values the PRNG generates is also `p`, and that it generates numbers from `0` to `p-1`.
• Now our algorithm is simple. We have two seeds, which we call `s` and `i`, both between `0` and `p-1`. `s` can be anything. `i` must be any number coprime to `p`. The nth element generated by the PRNG with seeds `s` and `i` is `(n * i + s) % p`. That is, multiply `i` by `n`, add `s`, and take the remainder when that value is divided by `p`.
• That gives you a sequence of incredibly crappy pseudo-random numbers that repeats with period `p` and never generates the same number within the period, and each number is between 0 and `p-1`. Enjoy.
• Let's work an example. `p=10`, `i=3`, `s=5`, the sequence is 5, 8, 1, 4, 7, 0, 3, 6, 9, 2 and then it repeats.
• Notice that the low bit of the sequence produced by this algorithm toggles on each subsequent step; that's really bad!
• You asked if any algorithm exists, not if any good algorithm exists.

That was really crappy. Can we do better?

Basically what you're asking is "I need a random permutation of this set". There are lots of good algorithms for that. Since there are `p!` permutations of a set with `p` unique items, what you have to do is uniformly choose a number between 0 and `p!-1`, and then generate a permutation from that number.

Generating the random seed is your problem; I describe how to turn it in to a permutation in my lengthy series on interesting properties of permutations, which you can read here:

https://ericlippert.com/2013/04/15/producing-permutations-part-one/

I doubt that such a PRNG exists, since it is simply not a very good PRNG. Not only do you know something about the next number in the sequence (whereas in a PRNG the whole point is that you don't know anything about the next number), but the longer the sequence gets, the more you know!

This is just a bad PRNG.

What you are talking about seems to be more a (pseudo-)random permutation than a (pseudo-)random number sequence.

Good pseudorandom number generator have a large period, for example C#'s implementation is more than 2⁵⁵

Since the next integer will be taken from the set of 2³² values, there will be repetitions long before its period is up.