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

Question

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.

Answer 1

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/

Answer 2

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.

Answer 3

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.