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!
