random cover of a range

dsimcha dsimcha at yahoo.com
Fri Feb 13 11:15:44 PST 2009


== 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.




More information about the Digitalmars-d mailing list