What is the optimal Jewish toenail cutting algorithm?

I am working on the software for a machine that will automatically trim toenails, so that users can simply put their feet in it and run it instead of having to manually do it by biting them or using nail clippers.

A sizeable percentage of our potential user base will likely be Jewish, and, evidently, there is a tradition about not trimming toenails (or fingernails) in sequential order

There seems to be dissenting opinion on the precise application of this tradition, but we think that the following rules are sufficient to accomodate people whose religious practices prohibit cutting toenails in order:

• No two adjacent toenails should be cut consecutively
• The cutting sequence on the left foot should not match the sequence on the right foot
• The cutting sequence on two consecutive runs should not be the same. The sequences shouldn't be easily predictable, so hardcoding an alternating sequence does not work.

This is how we have decided to number the toes:

5 4 3 2 1  1 2 3 4 5
Left foot  Right foot

I have written code to solve the problem, but the algorithm used is sub-optimal: in fact, the worst case performance is O(∞). The way it works is comparable to bogosort. Here is a pseudocode simplification of the actual code used:

function GenerateRandomSequence
   sequence = Array[5]
   foreach (item in sequence)
       item = RandomNumberBetween(1,5)
   return sequence

function GetToenailCuttingOrder
   while (true)
      sequence = GenerateRandomSequence()
      if (!AllItemsAreUnique(sequence))
         continue
      if (NoTwoAdjacentItemsHaveConsecutiveNumbers(sequence))
         return sequence

do
    leftFootSequence = GetToenailCuttingOrder()
    rightFootSequence = GetToenailCuttingOrder()
until (leftFootSequence != rightFootSequence &&
       leftFootSequence != leftFootSequenceFromLastRun &&
       rightFootSequence != rightFootSequenceFromLastRun)

Basically, it generates random sequences and checks if they meet the criteria. If it doesn't meet the criteria, it starts over. It doesn't take a ridiculously long amount of time, but it is very unpredictable.

I realize that the way I am currently doing it is pretty terrible, but I'm having trouble coming up with a better way. Can any of you suggest a more elegant and performant algorithm?

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]]

There's really no reason to introduce randomness into this problem. There are only 14 sequences that satisfy this problem, and surely some ordering of those sequences would best satisfy the aesthetic sense you're trying to accommodate. Thus, you should just reduce this problem to an algorithm for picking a sequence from those 14, probably in a pre-set order.

Javascript implementation of algorithm for finding the 14:

function swap (a, i, j) {
  var temp = a[i]
  a[i]=a[j]
  a[j]=temp
}

function permute (b, n, a) {
  if (n==4) {
    b.push(a.slice(0)) //copy array
  }
  else {
    for (var i = n; i < 5; i++) {
      swap(a,n,i)
      permute(b, n+1, a)
      swap(a,n,i)
    }
  }
}

var a = [1,2,3,4,5]
var b = []
var c = []

permute(b,0,a)

for (var i = 1; i < b.length-1; i++) {
  var good = true
  for (var j = 0; j < b[i].length; j++) {
    if (Math.abs(b[i][j-1]-b[i][j]) < 2 || Math.abs(b[i][j]-b[i][j+1]) < 2) {
      good = false
    }
  }
  if (good) c.push(b[i].join(''))
}

console.log(c)

EDIT: The new requirement that the sequences have to be generated randomly cannot be easily met. The best you can probably do is to generate them pseudorandomly, which is just as deterministic as hard-coding them ahead of time, and so should not satisfy anyone's superstitions.