title: What is the optimal Jewish toenail cutting algorithm?
body: <p>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.</p>
  
  <p>A sizeable percentage of our potential user base will likely be Jewish, and, evidently, there is a <a href="https://judaism.stackexchange.com/questions/1301/trimming-toenails-in-sequence">tradition about not trimming toenails</a> (<a href="https://judaism.stackexchange.com/questions/1118/rules-for-cutting-nails">or fingernails</a>) in sequential order </p>
  
  <p>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:</p>
  
  <ul>
  <li>No two adjacent toenails should be cut consecutively</li>
  <li>The cutting sequence on the left foot should not match the sequence on the right foot</li>
  <li>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.</li>
  </ul>
  
  <p>This is how we have decided to number the toes:</p>
  
  <pre><code>5 4 3 2 1  1 2 3 4 5
  Left foot  Right foot
  </code></pre>
  
  <p>I have written code to solve the problem, but the algorithm used is sub-optimal: in fact, the worst case performance is <strong>O(∞)</strong>. The way it works is comparable to <a href="http://en.wikipedia.org/wiki/Bogosort" rel="noreferrer">bogosort</a>. Here is a pseudocode simplification of the actual code used:</p>
  
  <pre class="lang-default prettyprint-override"><code>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 &amp;&amp;
         leftFootSequence != leftFootSequenceFromLastRun &amp;&amp;
         rightFootSequence != rightFootSequenceFromLastRun)
  </code></pre>
  
  <p>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.</p>
  
  <p>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?</p>