整数数组算法的排列
有一组例如（1,4,2,5,7,6,9,8,3）。 我们通过以下方式计算其first difference （FD）： firstDifference[i] = inputArray[i+1] - inputArray[i] 。 inputArray是原始集。 在示例中，情况是（1,4,2,5,7,6,9,8,3）。 firstDifference是通过以下方式从inputArray创建的：（inputArray的第二个元素） – （inputArray的第一个元素），依此类推。
所以给定集合的FD是（3，-2,3,2，-1,3，-1，-5）。 任务是找到给定集合的多个排列，其中第一个差异是FD的排列。 在示例中，我们应该找到（1,4,2,5,7,6,9,8,3）的这种排列，即第一个差异是（3，-2,3,2，-1,3， – 的排列）。 1，-5）。
这是我的算法：
- 找到给定集的所有排列。
- 找到给定集合的FD。
- 找出我们集合中排列的所有第一个差异。
- 仅选择这样的集合，其中第一个差异包含给定集合的FD的数量。 数数吧。
但是这个算法太慢了。 你能帮助创建更快的算法吗？ 可能我做了一些可以消除的步骤？
您不需要计算排列。 首先要注意的是，在您的示例中，差异数组中有17个可能的值，从-8到8，但实际数组只有五个不同的值。
创建一个矩阵并删除所有未发生的值（括号内）：
1 4 2 5 7 6 9 8 3 1 [0] 3 [1] [4] [6] [5] [8] [7] 2 4 [-3] [0] -2 [1] 3 2 [5] [4] -1 2 -1 2 [0] 3 [5] [4] [7] [6] [1] 5 [-4] -1 [-3] [0] 2 [1] [4] 3 -2 7 [-6] [-3] -5 -2 [0] -1 2 [1] [-4] 6 -5 -2 [-4] -1 [1] [0] 3 2 [-3] 9 [-8] -5 [-7] [-4] -2 [-3] [0] -1 [-6] 8 [-7] [-4] [-6] [-3] -1 -2 [1] [0] -5 3 -2 [1] -1 2 [4] 3 [6] [5] [0]
如果原始数组中的当前项目为1，则下一个项目必须为4或3，否则您将无法获得差异数组的排列。 您可以将此信息存储在图表中：
1 -> 4, 3 2 -> 1, 4, 5 3 -> 1, 2, 5, 6 4 -> 2, 7, 6, 3 5 -> 4, 7, 8, 3 6 -> 1, 4, 5, 9, 8 7 -> 2, 5, 6, 9 8 -> 7, 6, 3 9 -> 4, 7, 8
现在将目标差异数组转换为一个映射，在该映射中存储元素在数组中出现的频率：
count[-5]: 1 count[-2]: 1 count[-1]: 2 count[2]: 1 count[3]: 3
然后，您可以在图表中查找原始数组长度的路径。 您必须跟踪您是否已访问过某个节点。 你还应该通过递减“count”来跟踪你已经使用过的差异。 如果找到了所需长度的路径，则表示您具有有效的排列。
在伪代码中：
map count; set visited; function walk(a, left, path) { left--; if (left == 0) { print path; return; } a.visited = true; foreach (b in graph[a]) { d = b - a; if (count[d] > 0 && b.visited == false) { count[d]--; walk(b, left, path + [b]); count[d]++; } a.visited = false; } foreach (a in A) { walk(a, A.length, [a]); }
这是一个很大的问题…如果我正确理解你，你需要找到原始集的所有排列，以保持原始FD集的排列。
您的算法将起作用，除非您通过查看原始集的所有排列然后查看这些FD的所有排列来计算大量不必要的排列。 如果您首先查看原始FD的所有可能排列，您应该能够消除原始集合的一堆排列。
换句话说：
- 计算你的原始FD
- 找到原始FD的所有可能排列
- 然后线性地开始计算原始集的排列，但消除那些立即无法计算的排列。
例如：
设置{1,2,3,5} FD {1,1,2}
在计算此示例时，当您进入步骤3时，您应该能够自动消除以1,5开头的任何排列，因为4的差异永远不会出现在原始FD的任何排列中。 它只会在这个特定的例子中保存一些计算，但是一旦你开始使用更大的集合，这个算法就有可能为你节省大量的时间。