什么是最佳的犹太趾甲切割algorithm？
我正在开发一款能够自动修剪脚趾甲的机器的软件，以便用户可以简单地将它们放在脚上并运行，而不必通过咬或用指甲刀来手动操作。
我们的潜在用户群中有相当大的比例可能是犹太人，显然，有一个不按顺序修剪脚趾甲 （ 或指甲 ）的传统
似乎对这个传统的确切应用有异议，但是我们认为以下规则足以容纳宗教习惯禁止切割脚趾甲的人：
- 没有两个相邻的脚趾甲应该连续切割
- 左脚的切割顺序与右脚的顺序不符
- 连续两次的切割顺序不能相同。 序列不容易预测，所以硬编码交替序列不起作用。
这就是我们如何决定脚趾的数字：
5 4 3 2 1 1 2 3 4 5 Left foot Right foot 我已经编写了代码来解决这个问题，但是使用的algorithm是次优的：事实上，最糟糕的情况是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)
基本上，它产生随机序列并检查它们是否符合标准。 如果不符合标准，则重新开始。 这并不需要很长的时间，但是这是非常难以预料的。
我意识到我目前这样做的方式非常糟糕，但我很难找出一个更好的方法。 你们中的任何一个可以build议一个更优雅和高性能的algorithm？
你可以无限制地生成所有可能的脚趾甲切割序列，然后滤除违反犹太规则的所有序列。 幸运的是，人类每英尺只有五个脚趾，所以只有五个！ = 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(ab) == 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)
为了执行“不重复相同序列”规则，您可以select上述四个序列，并交替使用它们。 这里唯一的问题是，如果你把两个大脚趾算作“连续”，那么你就不能select两个以1开头的序列。
*您可能希望创build一个numberOfToesPerFootvariables，以便稍后如果您的任何客户的脚趾比您期望的更less，则可以轻松更改它。
有足够数量的序列可以满足您的要求。
- 生成{1,2,3,4,5}的所有排列。 只有120。
- 拒绝不符合要求的项目并永久存储剩余的项目。
- 随机挑选两个不同的序列。 记住你上次用过的那个。
编辑：如果这不是真的关于脚趾，但关于一些随机的问题，其中集可以大于5，序列空间变得非常大，在第二个脚上重复相同的序列的机会变得非常小。 所以随机生成序列并拒绝它们，如果它们匹配是一个好主意。 根据“跳两三跳，然后填空”等规则生成随机序列可能比产生随机排列和testing更快，如果“脚趾”数目很大，重叠的机会仍然很小。
其实，我最喜欢你原来的algorithm。
由于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次迭代即可find解决scheme。
千次迭代所需要的概率是多less？
那么，任何一次迭代失败的概率是104/120，所以失败1000次迭代的概率是（104/120）^ 1000，这个数字大概是10 ^（ – 63）。 也就是说，你永远不会看到它发生在你的有生之年，也可能不是在宇宙的一生中。
没有预先计算的表，容易适应不同数量的手指/脚趾/手/脚，容易适应不同的规则集…什么是不喜欢？ 指数衰减是一件美妙的事情。
[更新]
哎呀，我没有得到原来的公式错误…因为我的概率不等于1. 🙂
预期失败次数的正确expression式是：
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次迭代就可以find解决scheme（7.5次失败加上一次成功）。
我认为，我的“1000失败”案的math依然是正确的。
显而易见：find一个有效的订单，并对其进行硬编码。 但我不认为你想这样做。
你可以比你所做的更好地生成排列。 你不需要做拒绝抽样。 在最初sorting的排列（1,2，… 5）上使用Fisher Yates shuffle，你将有一个随机排列。 http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
但总的来说，生成和testing方法对我来说似乎是完全正确的，只要产生成功条目的可能性足够高。 我相信根据你的标准，有许多有效的序列，一旦你切换到一个随机排列，我怀疑你将不得不做许多拒绝迭代。
这里没有什么新东西，凯文已经发布了同样的解决scheme，但是我觉得很有趣，看看它如何转化为一种function性语言。 在这种情况下， 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}}
编辑
或者，更难以解释，但更短：
Reap[ Table[ If[Times @@ (Abs@Differences@i - 1) != 0, Sow@i], {i, Permutations@Range@5}]][[2, 1]]
这个问题真的没有理由引入随机性。 只有14个序列可以解决这个问题，当然这些序列的一些sorting最能满足你试图适应的审美意识。 因此，您应该将这个问题简化为从这14个中select一个序列的algorithm，可能是按照预先设定的顺序。
用JavaScript实现查找algorithm的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)
编辑：序列必须随机生成的新要求不能轻易满足。 你可能做的最好的事情就是伪随机地产生它们，这与确定性一样，提前对它们进行硬编码，所以不应该满足任何人的迷信。
