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

[Joseph Rushton Wakeling via Digitalmars-d]

On Thursday, 25 February 2016 at 17:27:25 UTC, Andrei 
Alexandrescu wrote:
> So we have 
> https://dlang.org/phobos/std_random.html#.randomCover which 
> needs to awkwardly allocate memory to keep track of the 
> portions of the array already covered.

Yes, this is definitely a standout in terms of being an 
unpleasant solution.  It means that you require o(N) memory even 
when you're dealing with a lazily-evaluated range -- it would 
probably be more efficient in practice to just write the input 
into an array and do an in-place shuffle. :-(

> 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.
>
> However, I've had difficulty finding such PRNGs. Most want the 
> maximum period possible so they're not concerned with a given 
> period. Any insights?

I'll try to see what I can find.  This must be something that 
other lazy/functional communities (Haskell, Clojure, ...) have 
had to contend with.

BTW I would caution that with pseudo-RNGs per se, the problem is 
not so much the size of the period per se, as the fact that it's 
not very random (in the sense that a PRNG is aiming for) to visit 
every possible value within the range of the RNG exactly once 
before repeating ... ;-)

> BTW I found this statement in the documentation rather odd: 
> "These issues will be resolved in a second-generation 
> std.random that re-implements random number generators as 
> reference types." The documentation is not a place for making 
> vague promises and speculations about future developments. I 
> think it should be removed.

Yes, I agree.  That was written at a time when those of us 
focused on std.random had great hope that a new design was 
immediately on the cards.  I can probably find the PRs if you 
want to see the context.