Sort array by pairwise difference

Question

For example we have the array X[n] = {X0, X1, X2, ... Xn} The goal is to sort this array that the difference between every pair is in ascending order.

For example X[] = {10, 2, 7, 4}

Answers are:

2 7 10 4
4 10 7 2

I have some code but it's brute force :)

#include <stdio.h>

int main(int argc, char **argv)
{
    int array[] = { 10, 2, 7, 4 };
    int a[4];

    for(int i = 0; i < 4; i++){
        a[0] = array[i];

        for(int j = 0; j < 4; j++){
            a[1] = array[j];
            if(a[0] == a[1])
               continue;

            for(int k = 0; k < 4; k++){
                a[2] = array[k];
                if(a[0] == a[2] || a[1] == a[2])
                    continue;

            for(int l = 0; l < 4; l++){
                a[3] = array[l];
                if(a[0] == a[3] || a[1] == a[3] || a[2] == a[3])
                    continue;
                if(a[0] - a[1] < a[1] - a[2] && a[1] - a[2] < a[2] - a[3])  
                    printf("%d %d %d %d\n", a[0], a[1], a[2], a[3]);
             }
         }
     }
   }
    return 0;
 }

Any idea for "pretty" algorithm ? :)

Answer 1

DISCLAIMER This solution will arrange items to difference grow by absolute value. Thx to @Will Ness

One solutions according to the difference between every pair is in ascending order requirement.

You just sort array in ascending order O(n)*log(n) and then start in the middle. And the you arrange elements like this :

[n/2, n/2+1, n/2-1, n/2+2, n/2-2, n/2+3 ...] you go to +1 first if more element are on the right side of (n/2)th element

[n/2, n/2-1, n/2+1, n/2-2, n/2+2, n/2-3 ...] you go to -1 first otherwise.

Here you get ascending pairwise difference.

NOTE!!! It is not guaranteed that this algo will find the smallest difference and start with it, but I do not see this is requirements.

Example

Sorted array: {1, 2, 10, 15, 40, 50, 60, 61, 100, 101}

Then, you pick 50 (as 10/2 = 5th), 60 (10/2+1 = 6), 40 and so on...

You'll get: {40, 50, 15, 60, 10, 61, 2, 100, 1, 101}

Which got you diffs: 10, 35, 45, 50, 51, 59, 88, 99, 100

Answer 2

Let's see. Your example array is {10,2,7,4} and the answers you show are:

2 7 10 4         
 5 3  -6     differences,  a[i+1] - a[i]

4 10 7 2
 6 -3 -5

I show the flipped differences here, it's easier to analyze that way.

So, the goal is to have the differences a[i+1] - a[i] in descending order. Obviously some positive difference values will go first, then some negative. This means the maximal element of the array will appear somewhere in the middle. The positive differences to the left of it must be in descending order of absolute value, and the negatives to the right - in ascending order of absolute value.

Let's take another array as an example: {4,8,20,15,16,1,3}. We start by sorting it:

1 3 4 8 15 16 20
 2 1 4 7  1  4      differences,  a[i+1] - a[i]

Now, 20 goes in the middle, and after it to the right must go values progressively further apart. Since the differences to the left of 20 in the solution are positive, the values themselves are ascending, i.e. sorted. So whatever's left after we pick some of them to move to the right of the maximal element, stays as is, and the (positive) differences must be in descending order. If they are, the solution is found.

Here there are no solutions. The possibilities are:

...  20 16 8    (no more)  left:  1 3 4 15    (diffs: 2 1 11 5) 
...  20 16 4    (no more)  left:  1 3 8 15    (diffs: 2 5 7 5)
...  20 16 3    (no more)  left:  1 4 8 15    (diffs: 3 4 7 5)
...  20 16 1    (no more)  left:  3 4 8 15  ....................
...  20 15 8    (no more)  left:  1 3 4 16
...  20 15 4    (no more)  left:  1 3 8 16
...  20 15 3    (no more)  left:  1 4 8 16
...  20 15 1    (no more)  left:  3 4 8 16
...  20 8       (no more)  left:  1 3 4 15 16
...  20 4       (no more)  left:  1 3 8 15 16
...  20 3       (no more)  left:  1 4 8 15 16
...  20 1       (no more)  left:  3 4 8 15 16
...  20         (no more)  left:  1 3 4 8  15 16

Without 1 and 3, several solutions are possible.

Answer 3

Solution for this problem is not always possible. For example, array X[] = {0, 0, 0} cannot be "sorted" as required because both differences are always equal.

In case this problem has a solution, array values should be "sorted" as shown on the left diagram: some subset of the values in ascending order should form prefix of the resulting array, then all the remaining values in descending order should form its suffix. And "sorted" array should be convex.

This gives a hint for an algorithm: sort the array, then split its values into two convex subsets, then extract one of these subsets and append it (in reverse order) at the end.

A simple (partial) implementation would be: sort the array, find a subset of values that belong to convex hull, then check all the remaining values, and if they are convex, append them at the end. This algorithm works only if one of the subsets lies completely below the other one.

If the resulting subsets intersect (as shown on the right diagram), an improved version of this algorithm may be used: split sorted array into segments where one of the subsets lies completely below other one (A-B, B-C), then for each of these segments find convex hull and check convexity of the remaining subset. Note that X axis on the right diagram corresponds to the array indexes in a special way: for subset intersections (A, B, C) X corresponds to an index in ascending-sorted array; X coordinates for values between intersections are scaled according to their positions in the resulting array.

Sketch of an algorithm

1. Sort the array in ascending order.
2. Starting from the largest value, try adding convex hull values to the "top" subset (in a way similar to Graham scan algorithm). Also put all the values not belonging to convex hull to the "bottom" subset and check its convexity. Continue while all the values properly fit to either "top" or "bottom" subset. When the smallest value is processed, remove one of these subsets from the array, reverse the subset, and append at the and of the array.
3. If after adding some value to the "top" subset, the "bottom" subset is not convex anymore, rollback last addition and check if this value can be properly added to the "bottom" subset. If not, stop, because input array cannot be "sorted" as required. Otherwise, exchange "top" and "bottom" subsets and continue with step 2 (already processed values should not be moved between subsets, any attempt to move them should result in going to step 3).

In other words, we could process each value of sorted array, from largest to smallest, trying to append this value to one of two subsets in such a way that both subsets stay convex. At first, we try to place a new value to the subset where previous value was added. This may make several values, added earlier, unfit to this subset - then we check if they all fit to other subset. If they do - move them to other subset, if not - leave them in "top" subset but move current value to other subset.

Time complexity

Each value is added or removed from "top" subset at most once, also it may be added to "bottom" subset at most once. And for each operation on an element we need to inspect only two its nearest predecessors. This means worst-case time complexity of steps 2 and 3 is O(N). So overall time complexity is determined by the sorting algorithm on step 1.