random cover of a range

[Bill Baxter]

On Fri, Feb 13, 2009 at 9:23 AM, Andrei Alexandrescu
<SeeWebsiteForEmail at erdani.org> wrote:
> Sean Kelly wrote:

>> Skip ahead a random number of elements before performing the linear
>> search.
>
> Can you prove this will yield a uniform cover?

I don't see how it could.  If you have a linear search at all, then
empty at the end of a row of filled elements will always have a higher
probability of getting chosen.

Pure dart throwing would clearly work though.  Just keep trying
randomly till you hit an empty.  Won't perform very well, though.

--bb