最佳的犹太脚趾甲切割算法是什么？

一尘不染

最佳的犹太脚趾甲切割算法是什么？

algorithm

我正在为会自动修剪脚趾甲的机器开发软件，以便用户可以简单地将脚放进去并运行它，而不必通过咬伤或使用指甲钳手动进行操作。

我们潜在用户群中有很大一部分可能是犹太人，而且很明显，有一种传统是不按顺序修剪脚趾甲（或指甲）

对于这种传统的确切应用，似乎存在不同意见，但是我们认为以下规则足以容纳宗教信仰禁止按趾甲切割的人：

不应连续切割两个相邻的脚趾甲
左脚的切割顺序应与右脚的切割顺序不匹配
连续两次切割的切割顺序不应相同。序列不应该容易预测，因此对交替序列进行硬编码是行不通的。

这就是我们决定对脚趾编号的方式：

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

我已经编写了代码来解决该问题，但是所使用的算法不是最优的：实际上，最坏的情况是 O（∞）
。它的工作方式可与bogosort媲美。这是使用的实际代码的伪代码简化：

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)

基本上，它会生成随机序列并检查它们是否符合条件。如果不符合条件，则重新开始。它并不需要很长的时间，但是这是非常不可预测的。

我意识到我目前的工作方式非常糟糕，但是我在想出更好的方法时遇到了麻烦。你们中的任何人都可以提出一种更优雅，更高效的算法吗？

阅读 299

2020-07-28

共1个答案

一尘不染

您可以无限制地生成所有可能的趾甲切割序列，然后过滤掉所有违反犹太规则的序列。幸运的是，人类每只脚只有五个脚趾*，所以只有五个脚趾！=
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)

要强制执行“没有相同序列的重复”规则，您只需选择上述四个序列，然后交替使用即可。这里唯一的问题是，如果您将两个大脚趾算作“连续的”，那么您将无法选择两个分别以1开头和结尾的序列。

*您可能希望创建一个numberOfToesPerFoot变量，因此，如果您的任何一个客户的脚趾比您预期的少或更多，您可以在以后轻松地进行更改。

2020-07-28