On 02.05.2017 22:42, MysticZach wrote:
On Tuesday, 2 May 2017 at 13:44:03 UTC, MysticZach wrote:
1. Test a random element in the array. If it satisfies P, return it.
2. Choose a hopper interval, h, that is relatively prime to the number
of elements in the array, n. You could do this by randomly selecting
from a pre-made list of primes of various orders of magnitude larger
than n, with h = the prime % n.
3. Hop along the array, testing each element as you go. Increment a
counter. If you reach the end of the array, cycle back to the
beginning starting with the remainder of h that you didn't use. I
think that h being relatively prime means it will thereby hit every
element in the array.
4. Return the first hit. If the counter reaches n, return failure.
Taking this a step further, it occurred to me that you could use *any*
hopping interval from 1 to array.length, if the length of the array were
prime. So artificially extend the array and just skip a jump when you
land in the extended area. And since you'd skip lots of jumps if the
extension were any bigger that the hopping interval, reduce its length
to modulo the hopping interval.
// returns a random index of array satisfying P(x), -1 if not found
int randomlySatisfy(A[] array) {
auto length = array.length;
if (!length)
return -1;
auto i = uniform(0, length);
auto hop = uniform(1, length);
// greatest prime < 2^^31, for simplicity
enum prime = 2147483477;
assert (length <= prime);
auto skipLength = ((prime - length) % hop) + length;
auto count = 0;
for (;;) {
if (P(a[i]))
return i;
++count;
if (count == length)
return -1;
i += hop;
if (i < length)
continue;
if (i < skipLength)
i += hop;
(I guess this should be 'while'.)
i -= skipLength;
}
return -1;
}
This solution is stupidly simple and I haven't tested it. But I believe
it's truly random, since the hopping interval is arbitrary. Who knows,
it might work.
Counterexample: [1,1,1,0,0]
Your algorithm returns 0 with probability 7/20, 1 with probability 6/20
and 2 with probability 7/20.
Note that there is a simple reason why your algorithm cannot work for
this case: it picks one of 20 numbers at random. The resulting
probability mass cannot be evenly distributed among the three elements,
because 20 is not divisible by 3.
