整数数组算法的置换

本文介绍了整数数组算法的置换的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

有一组，例如（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的第一元件）等

There is a set e.g.(1, 4, 2, 5, 7, 6, 9, 8, 3). We calculate its first difference (FD) the following way: firstDifference[i] = inputArray[i+1] - inputArray[i]. inputArray is original set. In example case is (1, 4, 2, 5, 7, 6, 9, 8, 3). firstDifference is created from inputArray the following way: (2nd element of inputArray) - (1st element of inputArray) and so on.

于是给定组的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）。

So the FD of given set is (3, -2, 3, 2, -1, 3, -1, -5). The task is to find a number of permutations of given set which first difference is a permutation of the FD. In example case we should find such permutations of (1, 4, 2, 5, 7, 6, 9, 8, 3) that first differences is permutation of (3, -2, 3, 2, -1, 3, -1, -5).

这是我的算法：

找到给定的所有排列。

找到给定的FD。

找到排列在我们组所有的第一个差异。

选择只有这样套，其中一阶差分包含给定的FD的数量。数得过来。

但是，该算法是太慢了。你能帮助创造更快的算法？也许我作出这样就可以消除一些步骤？

But this algorithm is too slow. Can you help to create faster algorithm? Probably I make some steps that can be eliminated?

推荐答案

您并不需要计算排列。要注意的第一件事情是，在你的榜样，你有17种可能的值在-8至8日在你的差异数组，但你实际的数组只有五个不同的值。

You don't need to calculate permutations. The first thing to note is that in your example you have 17 possible values from -8 to 8 in your difference array, but your actual array has only five different values.

请矩阵，并重拳出击不发生的所有值（在括号中）：

Make a matrix and strike out all values that don't occur (in brackets):

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，否则你不会得到你的差异阵列的排列。您可以在图中存储这些信息：

If your current item in the original array is 1, the next item must either be 4 or 3, otherwise you won't get a permutation of your difference array. You can store this information in a graph:

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

现在把你的目标差数组您存储多久的元素出现在数组中的地图：

Now turn your target difference array into a map where you store how often an element occurs in the array:

count[-5]: 1 count[-2]: 1 count[-1]: 2 count[2]: 1 count[3]: 3

然后你可以看一下原始数组的长度，在图形的路径。你必须保持跟踪你是否已经访问过的一个节点或没有。你也应该跟踪哪些差别你已经使用递减`count'。如果你已经找到了所需长度的路径，你有一个有效的置换。

Then you can look for paths of the original array's length in your graph. You have to keep track whether you have already visited a node or not. You should also keep track of which differences you have already used by decrementing `count´. If you have found a path of the desired length, you have a valid permutation.

在伪code：

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