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

Answer 2

This is a great problem... if I'm understanding you right you need to find all of the permutations of the original set that maintain a permutation of your original FD set.

Your algorithm will work except that you are calculating a lot of unnecessary permutations by looking at all permutations of the original set and then all the permutations of those FDs. If you look at all possible permutations of your original FD first, you should be able to eliminate a bunch of permutations of your original set.

So in other words:

1. Calculate your original FD
2. Find all possible permutations of the original FD
3. Then linearly begin calculating your permutations of your original set but eliminate those that immediately cannot be calculated.

For instance:

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

In calculating this example, when you get to step 3 you should automatically be able to eliminate any permutations that start with 1, 5 since the difference of 4 will never be in any permutation of your original FD. It will only save you a few calculations in this particular example but once you start working larger sets this algorithm has the potential to save you a significant amount of time.