random cover of a range

[Denis Koroskin]

On Sat, 14 Feb 2009 02:34:48 +0300, Jason House <jason.james.house at gmail.com> wrote:

> dsimcha Wrote:
>
>> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s  
>> article
>> > bearophile wrote:
>> > > Andrei Alexandrescu>The quest for finding a random cover of an array
>> > > with as little extra memory consumed and with good complexity is  
>> on!<
>> > >
>> > >
>> > > This thread is very long and complex, I am unable to understand  
>> where
>> > > to start reading, etc. So can someone explain the problem to me, so  
>> I
>> > > may be able to suggest some idea/code?
>> > Given an array of length m, return a range that iterates the array in
>> > random order such that the entire array is visited without going  
>> through
>> > the same element more than once. Consume minimal amounts of memory and
>> > time. Baseline solution: allocate an array of indices, shuffle it,  
>> then
>> > follow indices stored in the array.
>> > Andrei
>>
>> One important thing to add, since we already have a solution that would  
>> be good except for this
>> requirement:
>>
>> The frequency with which each of the N! permutations of each array  
>> occur must be uniform.
>>
>
> Believe it or not, that's an unreasonable requirement. IIRC, most RNG's  
> have periods such as 2^32. You can't get more permutations than that.  
> Somewhere in the ballpark of 17 elements, your requurement becones  
> impossible to meet without a highly specialized RNG. I hope someone can  
> prove me wrong about that!

You are wrong!

It's 13 elements :p