[解決済み] ユダヤ人の足の爪を切る最適なアルゴリズムとは？

質問

足の爪を噛んだり、爪切りを使ったりすることなく、足を入れて動かすだけで自動的に爪を切ってくれる機械のソフトウェアを作っています。

私たちの潜在的なユーザーのかなりの割合がユダヤ人であると思われます。 足の爪を切らないという伝統 ( または指の爪 ) を順番に表示する

この伝統の正確な適用については異論があるようですが、宗教上の理由で足の爪を順番に切ることを禁じている人々には、以下のルールで十分対応できると考えています。

• 隣接する 2 つの足の爪を連続して切ってはならない。
• 左足のカットの順番は、右足の順番と同じにしてはならない。
• 連続する2つのランのカッティングシーケンスは同じであってはなりません。シーケンスは簡単に予測できるものであってはならないので、交互のシーケンスをハードコーディングしてもうまくいかない。

このようにして、つま先の番号を決めることにしました。

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

この問題を解決するためのコードを書きましたが、使用されたアルゴリズムは最適とは言えません：実際、最悪の場合のパフォーマンスは O(∞) . その動作は ボゴソート . 実際に使用されるコードを擬似的に簡略化したものがこちらです。

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)

基本的にはランダムな配列を生成し、条件を満たしているかどうかをチェックします。条件を満たさない場合は、やり直しになります。とんでもなく長い時間がかかるわけではありませんが、非常に予測不可能です。

現在私が行っている方法はかなりひどいと理解していますが、より良い方法を思いつかず困っています。どなたか、よりエレガントでパフォーマンスの高いアルゴリズムを提案していただけないでしょうか。

どのように解決するのですか？

足の爪を切るシーケンスを無制限に生成し、ジュエルルールに違反するシーケンスをすべてフィルタリングすればよいのです。幸いなことに、人間には片足に5本の指しかないので*、制限のない配列は5！=120個しかないのです。

Pythonの例です。

#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)

同じ配列を繰り返してはいけないというルールを強制するには、上記の配列の中から4つを選び、交互に使用すればよいのです。ただ、もし2本の足の指を連続したものとして数えるなら、それぞれ1で終わる配列と1で始まる配列の2つを選ぶことはできないでしょう。

*クライアントの誰かが予想よりもつま先が少ない、または多いことが判明した場合、後で簡単に変更できるように、numberOfToesPerFoot 変数を作成するとよいでしょう。