[OT] Algorithm question

[Andrea Fontana via Digitalmars-d]

On Monday, 1 May 2017 at 04:15:35 UTC, H. S. Teoh wrote:
> 1) "Random shooting":
>
> 	auto r = ... /* elements of A */
> 	for (;;) {
> 		auto i = uniform(0, r.length);
> 		if (P(r[i])) return r[i];
> 	}
>
>    Advantages: If a large percentage of elements in A satisfy 
> P(x), then
>    the loop will terminate within a small number of iterations; 
> if the
>    majority of elements satisfy P(x), this will terminate well 
> below n
>    iterations.
>
>    Disadvantages: If only a small percentage of elements 
> satisfy P(x),
>    then this loop could take arbitrarily long to terminate, and 
> it will
>    not terminate at all if no elements satisfy P(x).
>

If you find an element that doesn't satisfy P(x) move it on top 
of array (swap!) and then try again with uniform(1, r.length - 1) 
and so on.

It terminates in this way.

Andrea