random cover of a range

[Jason House]

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.

Roll die to get x in 0..k. If x==0, select this element, otherwise decrement x.

 
> 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.

If x==0, return element, otherwise decrement x. This trick saves a lot of random number generation.

> This has O(n log n) complexity. 

O(n^2). 

> 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