整数排列算法

Question

有一个集合，例如（1,4,2,5,7,6,9,8,3）。我们通过以下方式计算它的第一个差异（FD）：first差异[i]=inputArray[i 1]-inputArray[i]。inputArray是原始集。例如大小写为（1,4,2,5,7,6,9,8,3）。first差异是从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)的排列。

这是我的算法:

< li >查找给定集合的所有排列。 < li >查找给定集合的FD。 < li >找出集合中所有排列的第一差。 < li >仅选择这样的集合，其中第一个差异包含给定集合的FD编号。数一数。

但是这个算法太慢了。你能帮助创建更快的算法吗？大概我做了一些可以消除的步骤？

Answer 1

这是一个很大的问题...如果我理解正确，您需要找到原始集合的所有排列，以保持原始FD集合的排列。

你的html" target="_blank">算法将会工作，除了你正在通过查看原始集合的所有排列，然后是那些FD的所有排列来计算许多不必要的排列。如果你首先查看你的原始FD的所有可能的排列，你应该能够消除你的原始集合的一堆排列。

换句话说:

1. 计算原始FD
2. 找到原始FD的所有可能排列。
3. 然后线性地开始计算原始集合的置换，但排除那些无法立即计算的置换

例如：

集合{1，2，3，5} FD {1，1，2}

在计算此示例时，当您到达步骤3时，您应该能够自动消除以1、5开头的任何排列，因为4的差异永远不会出现在您原始FD的任何排列中。在这个特定的示例中，它只会为您节省一些计算，但是一旦您开始处理更大的集合，这个算法就有可能为您节省大量时间。

Answer 2

您不需要计算排列。首先要注意的是，在您的示例中，差异数组中有17个可能的值，从-8到8，但实际数组只有5个不同的值。

创建一个矩阵并删除所有未出现的值（在括号中）：

        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

然后，您可以在图形中查找原始数组长度的路径。您必须跟踪您是否已经访问了一个节点。您还应该通过递减“计数”来跟踪您已经使用了哪些差异。如果您找到了所需长度的路径，那么您就有了有效的排列。

在伪码中：

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]);
}