整数数组的排列算法

Question

有一个集合，例如 (1, 4, 2, 5, 7, 6, 9, 8, 3)。我们按照以下方式计算它的 first difference（FD）: firstDifference[i] = inputArray[i+1] - inputArray[i]。其中inputArray是原始集合。在这个例子中，inputArray 是(1, 4, 2, 5, 7, 6, 9, 8, 3)，firstDifference 是从 inputArray 创建的，如下所示：(inputArray 的第二个元素) - (inputArray 的第一个元素)，以此类推。

因此，给定集合的 FD 是 (3, -2, 3, 2, -1, 3, -1, -5)。任务是找到给定集合的排列数，使其 first difference 是 FD 的排列。在这个例子中，我们需要找到 (1, 4, 2, 5, 7, 6, 9, 8, 3) 的这样的排列，使得它们的 first differences 是 (3, -2, 3, 2, -1, 3, -1, -5) 的排列。

下面是我的算法：

1. 找到给定集合的所有排列。
2. 找到给定集合的 FD。
3. 找到所有排列的 first differences。
4. 仅选择 first differences 中包含给定集合的 FD 数字的集合。计算它们的数量。

但是，这个算法太慢了。能否帮助创建更快的算法？也许我做了一些可以省略的步骤？

- user2950602

---

任务是找到给定集合的排列数量，其中第一个差异是FD的排列。你能详细解释一下吗？另外，如果您格式化您的问题，它会更易读，与您现在的文本块形成对比。 - Cruncher

请详细说明“FD的排列组合”。 - theGreenCabbage

你能详细解释一下“FD排列”的含义吗？ - user2950602

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

然后你可以在图中寻找原数组长度的路径。你必须跟踪是否已经访问过一个节点。你还应该通过减少“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]);
}

- M Oehm

---

这种类似深度优先搜索的方法肯定比原始的暴力尝试和已接受的答案（阶乘(!)复杂度）更快。虽然我不确定给定解决方案的确切复杂度是多少，但感觉仍然可以进行优化，例如任何解决方案集合中最后一个元素和第一个元素之间的距离（或“路径”）始终与原始集合中的“last”-“first”相同。无论如何，+1。 - kiruwka

我同意上一位发帖者的看法... 这肯定比我的原始答案更好。我喜欢从条目之间的差异入手来解决问题的想法，而不是查看单个排列。这肯定需要更多的开销来构建，但与我的算法相比，它将运行得非常快。干得好！ +1 - user2858650

Answer 2

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

您的算法将有效，但您正在计算很多不必要的排列，即查看原始集合的所有排列，然后查看那些FD的所有排列。如果您首先查看原始FD的所有可能排列，则应该能够消除一堆原始集合的排列。

换句话说：

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

例如：

Set {1,2,3,5} FD {1, 1, 2}

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

- user2858650

---

我无法理解的一件事是如何找到可以被消除的集合。为了找到永远不会出现在FD中的数字，我应该对原始集合做什么？ - user2950602

你打算如何找到给定集合的所有排列？基本上，你只需采用相同的逻辑，并在下一个数字产生不在你的FD中的差异时添加停止功能。 - user2858650