Sort the array so that the element difference a [i] -a [i + 1] <= a [i + 1] -a [i + 2]

Question

My mind has been blown away since I started last week, trying to sort an array of N elements by condition: the difference between two elements is always less than or equal to the following two elements. For example:

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

You can change this array as follows:

• {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 of the solutions I examined is simply shuffling the array and checking it every time if it is consistent with the conditions, an effective method for a small number of elements, but a lot of time or even impossible for a large number of elements.

Another tried to move elements around the array using loops, hoping to fulfill the requirements again, but again this method is very time-consuming and sometimes impossible.

Trying to find an algorithm has no result, but there must be something.

Thank you in advance.

Answer 1

I usually do not just provide the code, but this question intrigued me, so here is a brute force solution that may interest you.

The concept will always be slow, because the individual elements in the sorted list are not independent of each other, so they cannot be sorted using traditional O (N log N) algorithms. However, differences can be sorted in a way that simplifies the validation for the solution, and permutations can be checked in parallel to speed up 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 2

This condition is associated with differentiation. The (negative) difference between adjacent elements must be stable or increase 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]) 

Thus, the second derivative must be 0 or negative, which coincides with the fact that the first derivative remains unchanged or changes downward, for example, part of the upper half of the circle. This does not mean that the first derivative itself should start positive or negative, just so that it never changes up.

The problem algorithmically is that it cannot be simple, since you never compare only 2 list items, you will have to compare three at a time (i, i + 1, i + 2).

So, the only thing you know, except for random permutations, is given in Klas's answer (the values ​​first rise, if at all, and then fall, if at all), but it is not a sufficient condition, since you can have a positive 2nd derivative in its two sets (rise / fall).

So, is there a solution much faster than random shuffling? I can only think of the following argument (similar to Klas's answer). For a given vector, a solution is more likely if you divide the data into the 1st segment, which is growing or stable (not falling), and the second, which is falling or stable (not rising), and not one is empty. Probably, one could argue that the two segments should be approximately equal in size. A growing segment should have data that is closer to each other, and a falling segment should contain data that is further apart. Thus, you can start with the average value and look for data close to it, transfer them to the first set, then search for more widely spaced data and move them to the second set. Thus, a histogram can help.

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

Answer 3

Here is a solution based on a backtracking algorithm.

• Sort input array in unordered order.
• Start dividing the array values ​​into two subsets: place the largest element in both subsets (this will be the “middle” element), then put the second largest in an arbitrary subset.
• Place the rest of the elements in a subset sequentially. If this cannot be done without violating the “difference” condition, use a different subset. If both subsets are unacceptable, rollback and change previous decisions.
• Pay attention to one of the arrays created in step 3 and connect it to another array.

The Python implementation is presented below (it is not perfect, the worst defect is a recursive implementation: while recursion is quite common for backtracking algorithms, this particular algorithm works in linear time, and recursion is not suitable 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 create a good dataset to test this algorithm: a simple set of random numbers is too simple for this algorithm or does not have any solutions. Here I tried to create a collection that is “fairly complex” by combining two sorted lists, each of which satisfies the “difference” condition. However, this data set is processed in linear time. And I don’t know how to prepare any data set that would demonstrate the more than linear temporal complexity of this algorithm ...

Answer 4

Not that, since the difference must constantly increase, any solution will have the element first in ascending order, and then in descending order. The length of any of the two "suborders" can be equal to 0, therefore, the solution can consist of a strictly increasing 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 ascending order and B in descending order.

Combining two sorted sets: AB

Check if you have a solution.

Do this for all possible divisions in A and B.

Answer 5

Expanding on @ roadrunner66's analysis, the solution is to take the two smallest elements of the source array and make them the first and last in the target array; take the next two smallest elements and make them second and last; keep moving until all the elements are placed on the target. Note that one goes to the left, and which one to the right does not matter.

Sorting the original array makes the process easier (finding the smallest elements becomes trivial), so the time complexity is O(n log n) . The complexity of the space is O(n) because it requires a target array. I do not know if it can be done on the spot.