Sort an array so the difference of elements a[i]-a[i+1]<=a[i+1]-a[i+2]

Question

My mind is blown since I began, last week, trying to sort an array of N elements by condition: the difference between 2 elements being always less or equal to the next 2 elements. For example:

Α[4] = { 10, 2, 7, 4}

It is possible to rearrange that array this way:

• {2, 7, 10, 4} because (2 - ­7 = ­-5) < (7 - ­10 = -­3) < (10 - ­4 = 6)

• {4, 10, 7, 2} because (4 - ­10 = -­6) < (10 - ­7 = ­3) < (7 - ­2 = 5)

One solution I considered was just shuffling the array and checking each time if it agreed with the conditions, an efficient method for a small number of elements, but time consuming or even impossible for a larger number of elements.

Another was trying to move elements around the array with loops, hoping again to meet the requirements, but again this method is very time consuming and also sometimes not possible.

Trying to find an algorithm doesn't seem to have any result but there must be something.

Thank you very much in advance.

Answer 1

Here is a solution based on backtracking algorithm.

1. Sort input array in non-increasing order.
2. Start dividing the array's values into two subsets: put the largest element to both subsets (this would be the "middle" element), then place second largest one into arbitrary subset.
3. Sequentially put the remaining elements to either subset. If this cannot be done without violating the "difference" condition, use other subset. If both subsets are not acceptable, rollback and change preceding decisions.
4. Reverse one of the arrays produced on step 3 and concatenate it with other array.

Below is Python implementation (it is not perfect, the worst defect is recursive implementation: while recursion is quite common for backtracking algorithms, this particular algorithm seems to work in linear time, and recursion is not good for very large input arrays).

def is_concave_end(a, x):
  return a[-2] - a[-1] <= a[-1] - x

def append_element(sa, halves, labels, which, x):
  labels.append(which)
  halves[which].append(x)
  if len(labels) == len(sa) or split_to_halves(sa, halves, labels):
    return True
  if which == 1 or not is_concave_end(halves[1], halves[0][-1]):
    halves[which].pop()
    labels.pop()
    return False
  labels[-1] = 1
  halves[1].append(halves[0][-1])
  halves[0].pop()
  if split_to_halves(sa, halves, labels):
    return True
  halves[1].pop()
  labels.pop()

def split_to_halves(sa, halves, labels):
  x = sa[len(labels)]
  if len(halves[0]) < 2 or is_concave_end(halves[0], x):
    return append_element(sa, halves, labels, 0, x)
  if is_concave_end(halves[1], x):
    return append_element(sa, halves, labels, 1, x)

def make_concave(a):
  sa = sorted(a, reverse = True)
  halves = [[sa[0]], [sa[0], sa[1]]]
  labels = [0, 1]
  if split_to_halves(sa, halves, labels):
    return list(reversed(halves[1][1:])) + halves[0]

print make_concave([10, 2, 7, 4])

It is not easy to produce a good data set to test this algorithm: plain set of random numbers either is too simple for this algorithm or does not have any solutions. Here I tried to generate a set that is "difficult enough" by mixing together two sorted lists, each satisfying the "difference" condition. Still this data set is processed in linear time. And I have no idea how to prepare any data set that would demonstrate more-than-linear time complexity of this algorithm...

Answer 2

Expanding on the @roadrunner66 analysis, the solution is to take two smallest elements of the original array, and make them first and last in the target array; take two next smallest elements and make them second and next-to-last; keep going until all the elements are placed into the target. Notice that which one goes to the left, and which one to the right doesn't matter.

Sorting the original array facilitates the process (finding smallest elements becomes trivial), so the time complexity is O(n log n). The space complexity is O(n), because it requires a target array. I don't know off-hand if it is possible to do it in-place.

Answer 3

This condition is related to differentiation. The (negative) difference between neighbouring elements has to be steady or increasing with increasing index. Multiply the condition by -1 and you get

 a[i+1]-a[i] => a[i+2]-a[i+1] 

or

0 => (a[i+2]-a[i+1])- (a[i+1]-a[i])

So the 2nd derivative has to be 0 or negative, which is the same as having the first derivative stay the same or changing downwards, like e.g. portions of the upper half of a circle. That does not means that the first derivative itself has to start out positive or negative, just that it never change upward.

The problem algorithmically is that it can't be a simple sort, since you never compare just 2 elements of the list, you'll have to compare three at a time (i,i+1,i+2).

So the only thing you know apart from random permutations is given in Klas` answer (values first rising if at all, then falling if at all), but his is not a sufficient condition since you can have a positive 2nd derivative in his two sets (rising/falling).

So is there a solution much faster than the random shuffle? I can only think of the following argument (similar to Klas' answer). For a given vector the solution is more likely if you separate the data into a 1st segment that is rising or steady (not falling) and a 2nd that is falling or steady (not rising) and neither is empty. Likely an argument could be made that the two segments should have approximately equal size. The rising segment should have the data that are closer together and the falling segment should contain data that are further apart. So one could start with the mean, and look for data that are close to it, move them to the first set,then look for more widely spaced data and move them to the 2nd set. So a histogram might help.

[4 7 10 2] --> diff [ 3 3 -8] --> 2diff [ 0 -11]

Answer 4

I normally don't just provide code, but this question intrigued me, so here's a brute-force solution, that might get you started.

The concept will always be slow because the individual elements in the list to be sorted are not independent of each other, so they cannot be sorted using traditional O(N log N) algorithms. However, the differences can be sorted that way, which simplifies checking for a solution, and permutations could be checked in parallel to speed up the processing.

import os,sys
import itertools

def is_diff_sorted(qa):
  diffs = [qa[i] - qa[i+1] for i in range(len(qa)-1)]
  for i in range(len(diffs)-1):
    if diffs[i] > diffs[i+1]:
      return False
  return True

a = [2,4,7,10]
#a = [1,4,6,7,20]
a.sort()
for perm in itertools.permutations(a):
  if is_diff_sorted(perm):
    print "Solution:",str(a)
    break

Answer 5

Not that since the diffence should be ever-rising, any solution will have element first in rising order and then in falling order. The length of either of the two "suborders" may be 0, so a solution could consist of a strictly rising or strictly falling sequence.

The following algorithm will find any solutions:

Divide the set into two sets, A and B. Empty sets are allowed.

Sort A in rising order and B in falling order.

Concatenate the two sorted sets: AB

Check if you have a solution.

Do this for all possible divisions into A and B.