random cover of a range

[Andrei Alexandrescu]

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