Permutations of integer array algorithm

Question

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.

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).

Here's my algorithm:

1. Find all permutations of given set.
2. Find the FD of given set.
3. Find all first differences of permutations in our set.
4. choose only such sets, which first differences contains the numbers of FD of given set. Count them.

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

Answer 1

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]

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

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.

In pseudocode:

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