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

Question

我正在为一台能够自动修剪脚趾甲的机器开发软件,这样用户可以简单地将脚放入其中并运行它,而不必通过咬它们或使用指甲钳手动完成它.

我们潜在用户群的很大一部分可能是犹太人,显然,有一种传统是不按顺序修剪脚趾甲(或指甲)

对这一传统的确切应用似乎存在不同意见,但我们认为以下规则足以容纳宗教活动禁止切割脚趾甲的人:

• 不应连续切割两个相邻的脚趾甲
• 左脚的切割顺序不应与右脚的顺序相匹配
• 两次连续运行的切割顺序不应相同.序列不应该容易预测,因此对交替序列进行硬编码不起作用.

这就是我们决定给脚趾编号的方法:

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)

基本上,它会生成随机序列并检查它们是否符合标准.如果它不符合标准,它将重新开始.它不需要花费太长的时间,但它是非常难以预测的.

我意识到我现在这样做的方式非常糟糕,但是我遇到了一个更好的方法.你们中的任何人都可以建议一个更优雅,更高效的算法吗？

Answer 1

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

要强制执行"不重复相同序列"规则,您只需选择上述四个序列,然后交替使用它们.这里唯一的问题是,如果你把两个大脚趾算作"连续",那么你就不能选择两个分别结束并以1开头的序列.

*您可能想要生成一个numberOfToesPerFoot变量,因此如果您的任何客户的脚趾比您预期的要少或更多,您可以在以后轻松更改它.

Answer 2

有限数量的序列可满足您的要求.

1. 生成{1,2,3,4,5}的所有排列.只有120个.
2. 拒绝不满足要求的那些并存储剩余的集合(永久).
3. 随机选择两个不同的序列.记住你上次使用的是哪些.

编辑:如果这不是真的关于脚趾,但是关于集合可能远大于5的一些随机问题,序列空间变得非常大并且在第二只脚上重复相同序列的机会变得非常小.所以随机生成序列并在它们匹配时拒绝它们是一个好主意.根据某些规则生成随机序列,例如"跳过两三个,然后填充空白"可能比生成随机排列和测试更快,如果"脚趾"的数量很大,重叠的可能性仍然很小.

Answer 3

实际上,我最喜欢你的原始算法.

由于120个排列中有14个起作用,120个中的106个不起作用.因此每张支票的失败率为106/120.

这意味着预期的失败次数是:

1*(106/120) + 2*(106/120)^2 + 3*(106/120)^3 + ...

总结这个无限系列并不难:

S       = 1*x + 2*x^2 + 3*x^3 + ...

乘以x:

x*S     =       1*x^2 + 2*x^3 + ...

减去:

S - x*S = x + x^2 + x^3 + ...

再次乘以x再次减去:

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

由于x = 106/120,S = 64.9.

因此,平均而言,您的循环只需要65次迭代才能找到解决方案.

比如1000次迭代的概率是多少？

那么,任何单次迭代失败的概率是104/120,因此1000次迭代失败的概率是(104/120)^ 1000,这类似于10 ^( - 63).也就是说,你永远不会在你的一生中看到它发生,也可能不会在宇宙的生命周期中发生.

没有预先计算的表格,很容易适应不同数量的手指/脚趾/手/脚,很容易适应不同的规则集......有什么不喜欢的？指数衰减是一件很棒的事情.

[更新]

哎呀,我确实得到了原来的公式错误...因为我的概率不总和为1. :-)

预期失败次数的正确表达式为:

0*(14/120) + 1*(106/120)*(14/120) + 2*(106/120)^2*(14/120) + ...

(例如,要获得两次失败,您需要两次失败,然后成功.两次失败有概率(106/120)^ 2;一次成功有概率(14/120);将这些失败相乘以获得权重"2"一词.)

所以我的S偏离了因子(1-x)(即14/120).实际预期的故障数仅为x /(1-x)= 106/14 = 7.57.因此,平均而言,只需要8-9次迭代就可以找到解决方案(7.5次失败加一次成功).

我认为,我对"1000次失败"案的数学仍然是正确的.

Answer 4

显而易见:找到一个有效的订单,并对其进行硬编码.但我不认为你想这样做.

您可以比您的方式更好地生成排列.您不需要进行拒绝抽样.在初始排序的排列(1,2,... 5)上使用Fisher Yates shuffle,您将获得随机排列. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

但总的来说,生成和测试方法对我来说似乎完全没问题,只要生成成功条目的概率足够高.我确信根据你的标准有许多有效的序列,一旦你切换到随机排列,我怀疑你将不得不做很多拒绝迭代.