整数数组算法的置换 [英] Permutations of integer array algorithm

问题描述

有一组，例如（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).

这是我的算法：

1. 找到给定的所有排列。
2. 找到给定的FD。
3. 找到排列在我们组所有的第一个差异。
4. 选择只有这样套，其中一阶差分包含给定的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]);
}

这篇关于整数数组算法的置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！