random cover of a range

[Yigal Chripun]

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