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?

On Friday, 26 February 2016 at 12:23:24 UTC, Andrei Alexandrescu wrote:
> On 02/26/2016 03:34 AM, Joseph Rushton Wakeling wrote:
>> http://apfelmus.nfshost.com/articles/random-permutations.html
>
> This touches the input, we just want to cover it.
>
>> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150.9347&rep=rep1&type=pdf
>
> This seems like a nice article but I don't find a part relevant to this.

I may have misread, because I was in a rush this morning, but I thought that in section 2.3 it defined a method for lazily generating permutations of a list.  This was what I thought was relevant.

On Friday, 26 February 2016 at 12:23:24 UTC, Andrei Alexandrescu wrote:
> On 02/26/2016 03:34 AM, Joseph Rushton Wakeling wrote:
>> http://apfelmus.nfshost.com/articles/random-permutations.html
>
> This touches the input, we just want to cover it.

I thought the whole point of that article was that it described a method where there _wasn't_ reliance on mutable input that would be shuffled in-place?

On Friday, 26 February 2016 at 12:21:11 UTC, Andrei Alexandrescu wrote:
> On 02/26/2016 03:05 AM, Joseph Rushton Wakeling wrote:
>> I can probably find the PRs if you want to see the context.
>
> I understand the motivation behind that statement, and am not worried about pointing fingers etc. Would be great if a new PR removed the text. -- Andrei

Done. :-)

On Fri, Feb 26, 2016 at 09:26:54PM +0000, Joseph Rushton Wakeling via Digitalmars-d wrote:
> On Friday, 26 February 2016 at 12:21:11 UTC, Andrei Alexandrescu wrote:
> >On 02/26/2016 03:05 AM, Joseph Rushton Wakeling wrote:
> >>I can probably find the PRs if you want to see the context.
> >
> >I understand the motivation behind that statement, and am not worried about pointing fingers etc. Would be great if a new PR removed the text.  -- Andrei
> 
> Done. :-)

Merged. :-)


T

-- 
Let's call it an accidental feature. -- Larry Wall

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.

On Friday, 26 February 2016 at 23:05:00 UTC, John Colvin wrote:
> This was what I was trying to get at in my initial post, but I failed to get the idea across properly.

Yea.  It didn't even click with me at first, because when I first read Andrei's email I jumped straight in my head to the thought, "OK, so what _is_ an appropriate algorithm for lazily calculating a random permutation using O(1) storage space?"

The good news is that, AFAICS, that is a readily solvable problem.  It's inevitably more computationally complex than an in-place random shuffle -- O(n log n) instead of O(n) -- but algorithms do exist that could be adapted for Phobos.

On 02/26/2016 04:57 PM, H. S. Teoh via Digitalmars-d wrote:
> On Fri, Feb 26, 2016 at 09:26:54PM +0000, Joseph Rushton Wakeling via Digitalmars-d wrote:
>> On Friday, 26 February 2016 at 12:21:11 UTC, Andrei Alexandrescu wrote:
>>> On 02/26/2016 03:05 AM, Joseph Rushton Wakeling wrote:
>>>> I can probably find the PRs if you want to see the context.
>>>
>>> I understand the motivation behind that statement, and am not worried
>>> about pointing fingers etc. Would be great if a new PR removed the
>>> text.  -- Andrei
>>
>> Done. :-)
>
> Merged. :-)

Thank you folks!! -- Andrei