[OT] Algorithm question

[MysticZach via Digitalmars-d]

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 -= 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.