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
