Pseudo-random numbers in [0, n), covering all numbers in n steps?

Joseph Rushton Wakeling via Digitalmars-d digitalmars-d at puremagic.com
Fri Feb 26 11:35:38 PST 2016


On Thursday, 25 February 2016 at 17:27:25 UTC, Andrei 
Alexandrescu wrote:
> This could be fixed by devising a PRNG that takes a given 
> period n and generates all numbers in [0, n) in exactly n steps.

On reflection, I have a nasty feeling there's a fundamental 
problem with this proposed approach.

It's this: if you're relying on the PRNG having a period of n in 
which it covers exactly once each of the numbers from [0, n), 
then you're essentially outsourcing the random aspect of the 
permutation to the _seeding_ of this generator.

Now, what would be an appropriate seed-generation-mechanism to 
guarantee that this PRNG can select from all possible 
permutations with uniform probability?


More information about the Digitalmars-d mailing list