Reordering a list to maximize difference of adjacent elements

Question

I'm interested in reordering a list in such a manner as to maximize the sum of the squares of the differences between adjacent elements (cyclic). Here is a piece of Python code that brute-forces the solution in factorial time, so you can see what I mean:

def maximal_difference_reorder(input):

   from itertools import permutations

   best_sum = 0
   best_orderings = []

   for x in permutations(input):
        d = np.sum(np.diff(x)**2) + (x[0] - x[-1])**2
        if d > best_sum:
            best_orderings = [x]
            best_sum = d
        elif d == best_sum:
            best_orderings.append(x)

   return best_orderings

This yields the following results for maximal_difference_reorder(range(4)):

[(0, 2, 1, 3),
 (0, 3, 1, 2),
 (1, 2, 0, 3),
 (1, 3, 0, 2),
 (2, 0, 3, 1),
 (2, 1, 3, 0),
 (3, 0, 2, 1),
 (3, 1, 2, 0)]

As you can see, all the results are cyclic rotations and reflections of each other. If the score was determined with the sum of the differences, not squared, I believe all permutations would be evenly scored, given an evenly-spaced input.

Brute forcing works well, but O(n!) is terrible, so is it possible to do this in a smaller asymptotic computational time? Bonus points if it works for an uneven input mesh, or for other scoring functions.

Incidentally, this isn't homework or an interview question, though perhaps it would make a good one. Rather, I'm trying to generate a spectrum of colours for a series of parameterised data, and I'm trying to avoid having similar colours next to each other.

Answer 1

Your problem is a slightly disguised instance of the Traveling Salesman Problem.

Call the input list c (for "cities"). Pick any M which is an upper bound on (c[i]-c[j])**2 This is easily done in linear time since the min and the max of the list can be computed in a single pass, in which case M = (max - min)**2 works. Define the distance, d[i,j] from c[i] to c[j] by:

d(i,j) = 0 if i == j else M - (c[i]-c[j])**2

It is easy to see that for any cyclic permutation the cost of that permutation (computed according to d) is n*M - sum of squares of differences hence it is minimized if and only the sum of the squares of the differences is maximized.

There are a wealth of approaches to solving a TSP. Even though it is NP-hard, in practice state-of-the art methods are phenomenally good at solving problems that arise in practice. Furthermore, good heuristic methods can typically get to within a fraction of a percent of optimal.

Your particular problem is a special case of a TSP. As such it is possible that this special case is easier and in fact has a polynomial time solution, but I doubt it. I conjecture that it is NP-hard as well but don't have a proof. Also -- even if it is NP-hard, it might be that there is a solution (perhaps an Integer Programming formulation) which is more efficient than reducing it to TSP as above.

On Edit: based on comments by Dave Gavin and the answer by @SergeBallesta I now think that a polynomial time algorithm is possible. I'll leave this answer up, if for no other reason than if a polynomial time algorithm works then this problem would be a nice example for showing that certain subclasses of the TSP have simpler solutions.

Answer 2

If you are trying to maximize the squares of the differences between consecutive elements in a cyclic way, I would say that you should try to have the biggest element near to the smallest because conceptually a²+b²>=2*((a+b)/2)². That's what you have found by brute force with range(4).

I think that it could be shown by induction, but that part should be better asked on Mathematics but I would bet a coin that the solution is simply to:

• sort the list
• take biggest element put it in index 0 of result list
• take smallest one and put it on index 1
• take smallest of remaining and put it on index -1
• take biggest of remaining and put it on index 2

and iterate one time to the right and one to the left alternating biggest and smallest of remaining elements

You end in:

• O(n * log(n)) statistic for the sort with quicksort or merge-sort, or O(n²/2) with a mere bubble sort
• linear for building the result array