[OT] Algorithm question

[Timon Gehr via Digitalmars-d]

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.