[OT] Algorithm question

[Timon Gehr via Digitalmars-d]

On 01.05.2017 11:51, Moritz Maxeiner wrote:
> On Monday, 1 May 2017 at 04:15:35 UTC, H. S. Teoh wrote:
>>
>> Given a set A of n elements (let's say it's a random-access range of
>> size n, where n is relatively large), and a predicate P(x) that
>> specifies some subset of A of elements that we're interested in, what's
>> the best algorithm (in terms of big-O time complexity) for selecting a
>> random element x satisfying P(x), such that elements that satisfy P(x)
>> have equal probability of being chosen? (Elements that do not satisfy
>> P(x) are disregarded.)
>>
>> Which elements of A satisfy P(x) is not known ahead of time, nor is the
>> relative proportion of elements that satisfy P(x) or not.
>>
>
> Works only with a random access range and I haven't done the full
> analysis (and I'm a bit rusty on probability), but my first thought was
> random divide and conquer:
>
> ElementType!A* select(A,P)(A r)
> {
>   // Recursion anchor
>   if (r.length == 1) {
>     if (P(r[0])) return r[0];
>     else return null;
>   // Recurse randomly with p=0.5 into either the left, or right half of r
>   } else {
>     ElementType!A* e;
>     ElementType!A[][2] half;
>     half[0] = r[0..floor(r.length/2)];
>     half[1] = r[ceil(r.length/2)..$];
>
>     ubyte coinFlip = uniform(0,1) > 0;

This deterministically chooses 0. (uniform is right-exclusive.) I assume 
you mean uniform(0,2).

>     // Recurse in one half and terminate if e is found there
>     e = select(half[coinFlip]);
>     if (e) return e;
>     // Otherwise, recurse into other half
>     return select(half[1 - coinFlip]);
>   }
> }
>
> As stated above, I haven't done the full analysis, but intuitively
> speaking (which can be wrong, of course), the p=0.5 recursion ought
> satisfy the condition of elements satisfying P(x) being chosen
> uniformly;

Counterexample: [1,0,1,1].

The first element is chosen with probability 1/2, which is not 1/3.

> also intuitively, I'd expect the expected runtime for a
> uniform distribution of elements satisfying P(x)  to be around O(log N).

I don't understand this input model.

> Worst-case would be that it has to inspect every element in r once => O(N)