Andrei Alexandrescu Wrote: > Andrei Alexandrescu wrote: > > Andrei Alexandrescu wrote: > >> 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. > > > > Ok, here's something that should work. > > > > Start with array a of length a.length, allocate a bitmap with one bit > > per element in the map. Also the number of unselected elements left in > > the array is kept, call it k. > > > > To implement next(): > > > > 1. Walk from the beginning of the array to the first unselected element. > > > > 2. Roll a fair dice with k faces. If the dice chooses a specific face, > > choose that first unselected element. Otherwise continue. > > > > 3. Continue walking until the next unselected element. > > > > 4. Roll a fair dice with k-1 faces. If the dice chooses a specific face, > > choose that unselected element. Otherwise continue from step 3 using > > dices with k-1, k-2, ..., 1 faces. > > > > This has O(n log n) complexity. There is one obvious optimization: > > eliminate the first selected elements so we don't need to walk over them > > at each iteration. It's unclear to me how this affects complexity. > > > > > > Andrei > > This seems to work for forward ranges as well. I'll be darned. > > Andrei
Random ranges and forward ranges should have different implementations. Most notably, random ranges can avoid a lot of unnecessary calls to next.
