犹太人剪脚趾甲的最佳算法是什么？

我正在开发一个自动修剪脚趾甲的机器的软件，这样用户就可以简单地把脚放进去然后运行它，而不必通过咬脚趾甲或者使用指甲钳来手动修剪脚趾甲。

我们的潜在用户基础中很大一部分可能是犹太人，而且显然，有一个按顺序排列的 不修脚趾甲的传统(or fingernails)

对于这一传统的确切应用似乎存在不同意见书，但我们认为以下规则足以适应那些宗教习俗禁止为了修剪脚趾甲而修剪脚趾甲的人:

  • 不能连续剪两个相邻的脚趾甲
  • 左脚的切割顺序不应与右脚的切割顺序相匹配
  • 切割顺序在两个连续的运行不应该是相同的。序列不应该是容易预测的，所以硬编码交替序列不起作用。

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

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)

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

我意识到我现在做事的方式非常糟糕，但是我很难想出一个更好的方法。你们有谁能提出一个更优雅更高效的算法吗？

11236 次浏览
小开

显而易见的是: 找到一个有效的订单，并对其进行硬编码。但我觉得你不会想这么做的。

您可以比现在更好地生成排列。你不需要做排斥取样。在初始排序的排列(1,2，。.5) ，你会有一个随机的排列。http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

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

小开

有有限数量的序列可以满足您的需求。

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

编辑: 如果这不是关于脚趾的问题，而是关于一些随机的问题，其中集合可以大于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开始和以1结束的两个序列。

* 您可能需要创建 numberOfToesPerFoot 变量，这样，如果您的客户端的脚趾比您预期的要少，或者更多，您可以很容易地更改它。

小开

真的没有理由在这个问题中引入随机性。只有14个序列可以满足这个问题，当然，这些序列的一些排序将最好地满足您试图适应的美学感觉。因此，您应该将这个问题简化为从这14个序列中选择一个序列的算法，可能是按照预先设定的顺序。

Javascript 算法的实现寻找14:

function swap (a, i, j) {
var temp = a[i]
a[i]=a[j]
a[j]=temp
}


function permute (b, n, a) {
if (n==4) {
b.push(a.slice(0)) //copy array
}
else {
for (var i = n; i < 5; i++) {
swap(a,n,i)
permute(b, n+1, a)
swap(a,n,i)
}
}
}


var a = [1,2,3,4,5]
var b = []
var c = []


permute(b,0,a)


for (var i = 1; i < b.length-1; i++) {
var good = true
for (var j = 0; j < b[i].length; j++) {
if (Math.abs(b[i][j-1]-b[i][j]) < 2 || Math.abs(b[i][j]-b[i][j+1]) < 2) {
good = false
}
}
if (good) c.push(b[i].join(''))
}


console.log(c)

编辑: 不容易满足随机生成序列的新要求。你所能做的最好的事情可能就是伪随机地生成它们，这和提前硬编码它们一样具有决定性，因此不应该满足任何人的迷信。

小开

这里没有什么真正的新东西，同样的解决方案@Kevin 已经发布了，但我认为有趣的是看看它如何翻译成一种函数式语言。在这种情况下，Mathematica:

Extract[#,Position[Times @@ (Abs@#-1)&/@ Differences/@ #, Except@0, 1][[2 ;;]]]
&@ Permutations@Range@5

一些解释:

Permutations@Range@5 Calculates all permutations of {1, 2, 3, 4, 5}


Differences          Calculate the differences between adjacent elements
(we wish to discard all lists containing +1 or -1)


Times @@ (Abs@#-1)   Abs turns the -1s into +1s, and then to zeros by subtracting
one, then TIMES multiplies all elements, giving zero when
the original result of "Differences" contained a +1 or a -1


Position ... Except@0 Returns the position of the non zero results


Extract              Returns the original elements according to the calculated
positions

最终结果是:

\{\{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}}

Edit

或者，更难解释，但更简短:

Reap[ Table[ If[Times @@ (Abs@Differences@i - 1) != 0, Sow@i],
{i, Permutations@Range@5}]][[2, 1]]
小开

事实上，我最喜欢你的原始算法。

Since 14 out of 120 permutations work, 106 out of 120 do not. So each check has a 106/120 chance of failing.

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

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次迭代找到了一个解决方案。

比如说，它需要一千次迭代的概率是多少？

单次迭代失败的概率是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次失败”案例的计算仍然是正确的。


提交答案