random cover of a range

[Jason House]

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!