random cover of a range

[Andrei Alexandrescu]

Ok, following Leonardo's and Denis' ideas on covering an immutable array 
in random order, I thought about it and came up with one algorithm, in 
addition to the obvious one that stores one integer per element (see 
Denis' code).

Here's the algorithm. It stores one bit per element and takes O(n log n) 
time to cover a range of length n.

1. Given a random-access range r of length n, create a bitmap with one 
bit per element in r. The range is initially all zeros.

2. At each step, select a random index in the _original_ array, i.e. a 
random number in 0 .. r.length. Then walk upwards (with wrapping at the 
end of the range) until you find a bit = 0 in the bitmap. Mark that bit 
= 1 and return the found element.

3. The cover ends when all bits in the bitmap are 1.

I did a ballpark complexity estimate by approximating the average number 
of steps in (2) with n / (n - k), where k is the number of 1s in the 
bitmap. IIRC the average number of steps to hit a 1 in a binomial 
distribution with p = (n - k) / n is 1/p. Right? In that case, the total 
number of steps taken by the algo above is:

N = n / 1 + n / 2 + ... + n / (n - 1) = n * (1 + 1/2 + 1/3 + ... + 1/(n 
- 1)) < O (n log n)

Makes sense?

If the range does not offer random access, I think this algorithm will 
have quadratic complexity because it needs to make a number of steps 
proportional to n at each iteration.


Andrei