Andrei Alexandrescu wrote:
Yigal Chripun wrote:
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
what do you mean by "If the dice chooses a specific face"?
I don't understand this wording..
If you have a dice with 6 faces (the classic dice), a "specific face"
means you bet the dice will show e.g. "1" after rolling.
Andrei
oh, ok, thanks for clarifying
