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
