[OT] Algorithm question

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 1 May 2017 at 12:38:32 UTC, Andrea Fontana wrote:
> On Monday, 1 May 2017 at 12:31:48 UTC, Andrea Fontana wrote:
>> 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.
>
>
> Whoops i mean uniform(1, r.length) of course :)

I guess you meant to the end, but if mutating the array is ok, 
then you don't have to swap. Just move in the last element and 
chop 1 off the length.

Another cache-friendly mutation solution (assuming PRNG is cheap) 
is to have two phases:

Phase 1:
linear walkover the array and select elements with P(a[i])==true 
with probability 1/N
the overwrite the ones with P(a[i]) = false.

when done truncate the array.

Phase 2:
regular random selection from the array were all elements satisfy 
P.

The OP underspecified the requirements... There is a gazillion 
variations... :-P