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
