Arrange given numbers in a way such that the minimum absolute difference between any two consecutive numbers is maximized.

Question

I've been doing some competitive programming practice on Codeforces recently, and I stumbled upon a problem here. The solution to this problem can be found here.

Now, what if the set of numbers wasn't predetermined by $n$? Say that $n$ still denotes the size of the set, but has no bearing on the numbers in the set, e.g. we have a set $S$ of size $n = 5$, where $S = \{2, 6, 3, 7, 8\}$. How do we then still achieve the goal of maximizing $$\text{min}_{i=1}^{n-1}|p_{i+1}-p_i|$$ for a chosen permutation order $p_1, p_2, ..., p_n$? For my example above, I could see that the ideal arrangement orders would be $S = \{7,3,8,2,6\}$ or the reverse $S = \{6,2,8,3,7\}$ where $\text{min}_{i=1}^{n-1}|p_{i+1}-p_i| = 4$, but I'm not sure how to efficiently arrive at these permutations.

Answer 1

EDIT: turns out the following post is false.

The idea to turn it into a graph theory problem is still feasible. All it takes is replacing, at each of the O(n²) (in reality O(log n), with some dichotomy) steps, the O(n³) Warshall algorithm by a Bellman algorithm, or some variant, to test for the existence of a Hamiltonian path. But that is not polynomial, and my whole point was to show that it is possible to do better than exploring all possible permutations. Well, it is still better than O(n!). But certainly not better than a branch&bound search of best permutation.

So, in short, it is easy to salvage the idea "turn it into a graph theory problem: starts from complete graph, remove edges starging from the smallest one, and stop just before no solution can exist". But the idea is less interesting than I thought.

Since that graph is not any graph (for example, edges distance abide triangular inequality — [a,c].val < [a,b].val + [b,c].val to reuse my previous notation), maybe it is still feasible to find some other.

Former answer

One, certainly not optimal (it is $\mathcal{O}(n^5)$, and intuition is there should be at least a $\mathcal{O}(n^2)$ ; but at least, it is better than exploring all permutation, ie $\mathcal{O}(n!)$), way to solve it would be to build a complete graph with the numbers as nodes, and their absolute differences as edges.

Then, iterate all the edges, and removing the edge with minimal value. Check if the graph is still connected. That first edge that your remove that make the graph unconnected has the minimal absolute value you are looking for. And to find a permutation, you just need to find a chain passing through all nodes in the graph with the remaining edge (including that last one that you removed. That is, the last connected graph). With a hint: the starting node is the one that you disconnected when removing the last edge.

A pseudo code (it is written in a python-like language I wrote for my graph-theory class)

# build graph from a list of values
def buildGraph(l):
   for n in l:
      x=Sommet ("S"+n) # Create a node. That is a franglish language
      x.val=n          # create a node attribute for the number
   num=0
   # Iterate all pairs of nodes to create edges
   for s1 in sommets():
      for s2 in sommets():
         if s1.val>=s2.val: continue # avoid loops and redundant A-B / B-A edges
         a=Arete [s1,s2] # Create an edge between s1 and s2
         a.val = abs(s1.val-s2.val) # with the absolute difference as attribute

# Your example
f([2,6,3,7,8])

# Trim the graph (remove all unnecessary edges, starting from the 
# smallest ones)
def trimGraph():
   while True:
      (i,j)=min(aretes(), this.val) # Edge with minimal 'val' attribute
      v=(i,j).val  # 'val' attribute of that edge (that unpythonic syntax 
          # is specific to the lab language — whose spec is: if enough student
          # try a strange syntax, then it should be legal)
       effacer((i,j)) # Remove that edge
       # Test if graph is connected. Adj is the adjacency matrix
       # Wrong answer: a lazy, O(n³log n) way in lieu of a O(n³) Roy-Warshall, O(n³).
       #if 0 in ((Id.+Adj).**(n-1)):
       # Correct answer is to test if there is still a hamiltonian path after we removed that edge. See wiki for bellman algorithm for that.
       if not bellmanHamiltonianPathExists():
           Arete [i,j] # Put back the edge
           return v # Return the minimum absolute value in the best solution

That only provides you the minimum difference in the solution, as well as a graph with only the necessary edges. You still need to find a path in that graph that traverses all nodes. Which is another problem, that has some well-known solutions. For example here

That is just a hint anyway. I am pretty sure that the algorithm could be optimized (for example, connection test should not be a full Warshall at each step: we just need to check if one edge — the one we intend to remove — is necessary for connexity. That is an easier problem. That has some well known solutions as well. I was quite lazy here). And probably some better algorithm exist (I mean, besides optimisations of this one)

But point is, it is polynomial.

It is probable that a good branch&bound algorithm (explore all possible permutations, but cutting whole branches when they cannot provide a better solution than the best known one, and exploring with an heuristic) would be faster, in practice, but theoretically $\mathcal{O}(n!)$ (or at least, it would be quite hard to prove otherwise)