java - 整数数组排列算法

Question

有一个集合，例如(1, 4, 2, 5, 7, 6, 9, 8, 3)。我们通过以下方式计算其一阶差分 (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).

这是我的算法:

1. 找到给定集合的所有排列。
2. 找到给定集合的 FD。
3. 找到我们集合中排列的所有一阶差分。
4. 只选择这样的集合，其中第一个差异包含给定集合的 FD 数。数一数。

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

Answer 1

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

制作一个矩阵并删除所有不出现的值(在括号中):

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