On Sat, 14 Feb 2009 02:34:48 +0300, Jason House <[email protected]>
wrote:
dsimcha Wrote:
== Quote from Andrei Alexandrescu ([email protected])'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
