[OT] Algorithm question

[H. S. Teoh via Digitalmars-d]

On Mon, May 01, 2017 at 12:31:48PM +0000, Andrea Fontana via Digitalmars-d wrote:
> 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.
[...]

The problem is that swapping elements is not allowed for this particular
problem.  If swapping was allowed this would be a much easier problem to
solve. :-)


T

-- 
Chance favours the prepared mind. -- Louis Pasteur