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
