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

John Colvin via Digitalmars-d digitalmars-d at puremagic.com
Fri Feb 26 15:05:00 PST 2016


On Friday, 26 February 2016 at 19:35:38 UTC, Joseph Rushton 
Wakeling wrote:
> 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?

This was what I was trying to get at in my initial post, but I 
failed to get the idea across properly.


More information about the Digitalmars-d mailing list