random cover of a range

[Andrei Alexandrescu]

bearophile wrote:
> Andrei Alexandrescu:
>> 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.
> 
> I have faced such problem more than once, and I have tried to solve it in various ways. The faster solution was:
> - create an array of m bits, set to zero
> - Use a random generator to generate integer numbers in [0, m-1], if the corresponding big is set, extract another random number, if it's not set then set it, increment a counter, and return the array item that corresponds to the bit.
> - When about 90% of the bits is set, create an array with the remaining 10% items of the array, shuffle them in place with the usual algorithm by Knuth, and return them.

A quadratic algorithm applied to a fixed fraction of the input size will 
still yield quadratic behavior. I understand how your solution may be 
practical for a variety of needs, but if something is to be put in 
Phobos, we need something principled.

Andrei