What is the optimal Jewish toenail cutting algorithm?

Question

You could generate all possible toenail cutting sequences with no restrictions, and then filter out all sequences that violate the jewish rule. Luckily, humans only have five toes per foot*, so there are only 5! = 120 unrestricted sequences.

Python example:

#seq is only valid when consecutive elements in the list differ by at least two.
def isValid(seq):
    for i in range(len(seq)-1):
        a = seq[i]
        b = seq[i+1]
        if abs(a-b) == 1:
            return False
    return True


from itertools import ifilter, permutations
validseqs = ifilter(isValid, permutations([1,2,3,4,5]))
for i in validseqs:
    print i

(1, 3, 5, 2, 4)
(1, 4, 2, 5, 3)
(2, 4, 1, 3, 5)
(2, 4, 1, 5, 3)
(2, 5, 3, 1, 4)
(3, 1, 4, 2, 5)
(3, 1, 5, 2, 4)
(3, 5, 1, 4, 2)
(3, 5, 2, 4, 1)
(4, 1, 3, 5, 2)
(4, 2, 5, 1, 3)
(4, 2, 5, 3, 1)
(5, 2, 4, 1, 3)
(5, 3, 1, 4, 2)

To enforce your "no repeats of the same sequence" rule, you can just choose four of the above sequences, and use them alternately. The only catch here is that if you count the two big toes as "consecutive", then you can't choose two sequences that end and begin with 1, respectively.

*You may want to make a numberOfToesPerFoot variable, so you can easily change it later if any of your clients turn out to have less toes than you expect, or more.

There is a finite number of sequences that satisfy your requirements.

1. Generate all permutations of {1,2,3,4,5}. There are only 120.
2. Reject the ones that don't satisfy the requirements and store the remaining set (permanently).
3. Randomly pick two different sequences. Remember which ones you used last time.

EDIT: If this isn't really about toes, but about some random problem where the set can be much larger than 5, the sequence space becomes very large and the chance of repeating the same sequence on the second foot becomes very small. So randomly generating sequences and rejecting them if they match is a good idea. Generating random sequences according to some rule like "hop by twos or threes, then fill in the blanks" will probably be faster than generating random permutations and testing, and the chance of overlap will still be small if the number of "toes" is large.

Actually, I like your original algorithm best.

Since 14 out of 120 permutations work, 106 out of 120 do not. So each check has a 106/120 chance of failing.

That means the expected number of failures is:

1*(106/120) + 2*(106/120)^2 + 3*(106/120)^3 + ...

Not too hard to sum this infinite series:

S       = 1*x + 2*x^2 + 3*x^3 + ...

Multiply through by x:

x*S     =       1*x^2 + 2*x^3 + ...

Subtract:

S - x*S = x + x^2 + x^3 + ...

Multiply through by x again and subtract again:

x*S - x^2*S = x^2 + x^3 + ...
S - 2*x*S + x^2S = x
S*(1-x)^2 = x
S = x/(1-x)^2

Since x = 106/120, S = 64.9.

So, on average your loop needs only 65 iterations to find a solution.

What is the probability that it takes, say, one thousand iterations?

Well, the probability of failing any single iteration is 104/120, so the probability of failing 1000 iterations is (104/120)^1000, which is something like 10^(-63). That is, you will never see it happen in your lifetime, and probably not in the lifetime of the universe.

No precomputed tables, easy adaptation to different numbers of fingers/toes/hands/feet, easy adaptation to different rulesets... What's not to like? Exponential decay is a wonderful thing.

[update]

Whoops, I did get the original formula wrong... Since my probabilities do not sum to 1. :-)

The correct expression for the expected number of failures is:

0*(14/120) + 1*(106/120)*(14/120) + 2*(106/120)^2*(14/120) + ...

(For example, to get exactly two failures, you need two failures followed by a success. Two failures have probability (106/120)^2; one success has probability (14/120); multiply those together to get the weight for the "2" term.)

So my S is off by a factor of (1-x) (i.e., 14/120). The actual expected number of failures is just x/(1-x) = 106/14 = 7.57. So on average it takes only 8-9 iterations to find a solution (7.5 failures plus one success).

My math for the "1000 failures" case is still correct, I think.

The obvious: Find one order that works, and hard code it. But I don't think you want to do that.

You can generate permutations much better than the way you are doing it. You don't need to do rejection sampling. Use a Fisher Yates shuffle on an initially sorted permutation (1, 2, .. 5), and you'll have a random permutation. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

But in general, the generate and test method seems totally fine to me, so long as the probability of generating a successful entry is high enough. I am sure there any many valid sequences according to your criteria, once you switch to a random permutation, I doubt you'll have to do many rejection iterations.

Nothing really new here, the same solution @Kevin already posted, but I think interesting to see how it translates to a functional language. In this case, Mathematica:

Extract[#,Position[Times @@ (Abs@#-1)&/@ Differences/@ #, Except@0, 1][[2 ;;]]]  
         &@ Permutations@Range@5

Some explanations:

Permutations@Range@5 Calculates all permutations of {1, 2, 3, 4, 5}

Differences          Calculate the differences between adjacent elements
                     (we wish to discard all lists containing +1 or -1)

Times @@ (Abs@#-1)   Abs turns the -1s into +1s, and then to zeros by subtracting
                     one, then TIMES multiplies all elements, giving zero when 
                     the original result of "Differences" contained a +1 or a -1

Position ... Except@0 Returns the position of the non zero results

Extract              Returns the original elements according to the calculated 
                     positions

The final result is:

{{1, 3, 5, 2, 4}, {1, 4, 2, 5, 3}, {2, 4, 1, 3, 5}, {2, 4, 1, 5, 3}, 
 {2, 5, 3, 1, 4}, {3, 1, 4, 2, 5}, {3, 1, 5, 2, 4}, {3, 5, 1, 4, 2}, 
 {3, 5, 2, 4, 1}, {4, 1, 3, 5, 2}, {4, 2, 5, 1, 3}, {4, 2, 5, 3, 1}, 
 {5, 2, 4, 1, 3}, {5, 3, 1, 4, 2}}

Edit

Or, more difficult to explain, but shorter:

Reap[ Table[ If[Times @@ (Abs@Differences@i - 1) != 0, Sow@i],
           {i, Permutations@Range@5}]][[2, 1]]