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.

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?

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.


Thanks,

Andrei

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.
>
> 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 don't think that's a good idea. A prng is closed path through a state space and it doesn't matter where you start on said path, you're going to follow the same closed path through the state space.

I don't know of an algorithm for generating random permutations that isn't in-place (or O(N) storage), but I'm not an expert on the topic so maybe one does exist.

On 02/25/2016 01:19 PM, John Colvin wrote:
> I don't think that's a good idea. A prng is closed path through a state
> space and it doesn't matter where you start on said path, you're going
> to follow the same closed path through the state space.

That's totally fine for some applications - those that simply want to iterate the input at most once in a random order. Far as I can tell this is the most frequent. I don't care for a second iteration to guarantee a different iteration schedule. And if I did, I'd have no trouble reseeding the generator. -- Andrei

On Thursday, 25 February 2016 at 18:19:56 UTC, John Colvin wrote:
> I don't know of an algorithm for generating random permutations that isn't in-place (or O(N) storage), but I'm not an expert on the topic so maybe one does exist.

These might be relevant:

http://stackoverflow.com/questions/10054732/create-a-random-permutation-of-1-n-in-constant-space

http://stackoverflow.com/questions/32182120/to-generate-random-permutation-of-a-array-in-on-time-and-o1-space

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.
>
> 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?
>
> 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.
>
>
> Thanks,
>
> Andrei

The technical name for the property of distribution you describe is
 k-Dimensional Equidistribution (in this case k=1).
I would suggest taking a look at http://www.pcg-random.org.
They claim to have both arbitrary period and k-Dimensional Equidistribution

Nic

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.

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

On Friday, 26 February 2016 at 08:12:18 UTC, Joseph Rushton Wakeling wrote:
> 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. :-(

Also: I don't have the access to determine if this is really on the money, but looks like it could be promising: http://www.sciencedirect.com/science/article/pii/S0020019098001276

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. :-(
>
>> 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.

A few potential lines of exploration here:
http://apfelmus.nfshost.com/articles/random-permutations.html
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150.9347&rep=rep1&type=pdf

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. :-(
>
>> 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.

Last few links:
https://www.quora.com/What-is-the-most-efficient-way-to-randomize-shuffle-a-linked-list?share=1
https://en.wikipedia.org/wiki/Gilbert%E2%80%93Shannon%E2%80%93Reeds_model
https://stackoverflow.com/questions/12167630/algorithm-for-shuffling-a-linked-list-in-n-log-n-time/27624106#27624106