random cover of a range

[Steven Schveighoffer]

"Steven Schveighoffer" 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.
>
>
> This significantly increases the runtime by executing the random number 
> algorithm up to k-1 times per element.
>
> How is this different than just a linear search through the sparse array 
> for the random(0..k)th unused element?
>
> But I do concur that it provides a uniform map.  However, wouldn't the 
> worst runtime be O(n^2)?  i.e. k + k-1 + k-2 + k-3... + 1 iterations == k 
> *(k+1) / 2?  I'm not sure if average runtime is going to be O(nlgn).

Average runtime is still going to be O(n^2), because the average element 
chosen should be k / 2 elements into the range.

-Steve