问题描述
我工作的软件，一台机器，将自动修剪脚趾甲，使用户可以简单地把他们的脚在里面，并运行有它，而不是咬他们或用指甲刀做手工。
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
似乎对这一传统的precise应用程序中不同的意见，但我们认为以下规则足以容纳人，他们的宗教习俗禁止剪脚趾甲依次是：
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:
- 在任何两个相邻的脚趾甲应连续砍
- 在左脚的切割顺序不应该在右脚 的序列匹配
- 在两个连续运行的切削顺序不应该是相同的。该序列不应该轻易predictable，所以硬编码的交替序列不起作用。
这是我们如何决定编号脚趾：
This is how we have decided to number the toes:
5 4 3 2 1 1 2 3 4 5
Left foot Right foot
我已经写了code来解决问题，但所使用的算法是次优：其实，最坏的情况下性能 O（∞）。它的工作方式是媲美 BOGO排序。下面是实际code伪code简化使用：
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)
基本上，它生成随机序列，并检查他们是否符合标准。如果它不符合标准，它重新开始。它并不需要一个很长的离谱的时间，但它是非常不predictable。
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.
我意识到，这样我目前做的是pretty的可怕，但我有想出更好的办法麻烦。可以任你提出一个更优雅和高性能的算法？
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?
推荐答案
您可以生成所有可能的趾甲切割顺序没有任何限制，然后筛选出违反犹太教规则的所有序列。幸运的是，人类只有五个脚趾每英尺*，所以只有5！ = 120无限制的序列。
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的例子：
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)
要执行你的无重复相同的序列的规则，你可以选择四种以上的序列，并利用它们交替。在这里，唯一的缺点是，如果算上两个大脚趾为连续，那么你就不能选择结束两个序列，并开始与1，分别为。
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.
*您可能想使一个numberOfToesPerFoot变量，因此，您可以在以后很容易地改变，如果你的任何客户端的变成少的脚趾比预期，或更多。
*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.
这篇关于什么是最佳的犹太趾甲切割算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！