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 00:12:18 PST 2016
On Friday, 26 February 2016 at 08:05:09 UTC, Joseph Rushton
Wakeling wrote:
> 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. :-(
Some interesting discussion/ideas here:
https://cs.stackexchange.com/questions/29822/lazily-computing-a-random-permutation-of-the-positive-integers
More information about the Digitalmars-d
mailing list