Find a permutation $x_{\sigma(1)},\ldots,x_{\sigma(n)}$ of $x_1,\ldots,x_n$ that maximises $\sum_{k=1}^{n-1}\vert x_{\sigma(k)}-x_{\sigma(k+1)}\vert.$

Question

Suppose $\ x_1,\ x_2,\ \ldots,\ x_n\ $ are real numbers with $\ x_1 < x_2 <\ldots < x_n.$

Is there an efficient way to find a permutation $\ x_{\sigma(1)},\ x_{\sigma(2)},\ \ldots,\ x_{\sigma(n)}\ $ of $\ x_1,\ x_2,\ \ldots,\ x_n\ $ which maximises $\ f\left(\ \left( x_{\sigma(1)},\ x_{\sigma(2),\ \ldots,\ x_{\sigma(k)} } \right)\ \right) = \displaystyle\sum_{k=1}^{n-1} \left\vert x_{\sigma(k)} - x_{\sigma(k+1)} \right\vert\ ? $

My intuition tells me that either $\ f(\ \left(x_1,\ x_n,\ x_2,\ x_{n-1},\ x_3,\ x_{n-2},\ \ldots)\ \right)\ $ or $\ f(\ \left(x_n,\ x_1,\ x_{n-1},\ x_2,\ x_{n-2},\ x_3,\ \ldots\ \right)\ )\ $ might be a maximum, but I am not sure about this or how to prove if this is true.

Edit: my intuition is wrong. For example, take $\ x_1= 1,\ x_2 = 2,\ x_3=3,\ x_4=4.$ Then neither $\ x_1\to x_4\to x_2 \to x_3,\ $ nor $\ x_4\to x_1 \to x_3\to x_2\ $ are the longest route (both have length $6$), since $\ x_3\to x_1\to x_4\to x_2\ $ is longer with length $7$.

Answer 1

You can solve this as a maximum traveling salesman problem in which the customers are located on a number line and the cost to and from a dummy depot is $0$.

See Mathematics Magazine Problem 1654 for a similar problem where the depot is the origin and customer $k$ is located $k$ units to the right of the depot.

Answer 2

The answer to your question is YES, there is an efficient algorithm. Initially there are $n!$ candidates to test for maximality, but I show below that you can limit the search to just a special set of at most $n+1$ permutations (see the corollary at the end of this answer), which gives us linear complexity.

Intuitively, it seems that the logical way to construct a solution $\sigma$ is to define successively $\sigma(1),\sigma(2),\ldots,\sigma(n)$ in such a way that at each stage, $\sigma(j)$ is the farthest possible from $\sigma(j-1)$ among the remaining allowed values, in order to maximize the summand $|\sigma(j)-\sigma(j-1)|$ (and this idea turns out to be partially correct and leads to an efficient algorithm as I am going to explain).

If we apply this construction to the initial seed $\sigma(1)=k,\sigma(2)=n$, (where $1\leq k \leq n$), we obtain a permutation $\alpha_{n,k}$, going $(k,n,1,n-1,2,n-2,\ldots )$ and uniquely defined by

$$ \alpha_{n,k}(t)=\left\lbrace\begin{array}{rcl} k & \textrm{if} & t=2j-1, \ j=1 \\ j-1 & \textrm{if} & t=2j-1, \ 1\lt j\leq k \\ j & \textrm{if} & t=2j-1, \ k\lt j \\ n+1-j & \textrm{if} & t=2j, \ 1\lt j\leq n-k \\ n-j & \textrm{if} & t=2j, \ n-k\lt j \\ \end{array}\right.\tag{1} $$

where some cases may be empty according to the values of $k$. It must be emphasized that (1) above rigourously defines a unique permutation of $[|1..n|]$ for every $k\in [|1..n|]$, even on the edge cases $k=1$ or $n$ (to check that $\alpha_{n,k}$ is always a permutation, notice that the second and fifth cases together define a bijection with image $[|1..(r-1)|]$, while the third and fourth together define a bijection with image $[|(r+1)..n|]$).

Similarly, the initial seed $\sigma(1)=k,\sigma(2)=1$ leads to a permutation $\beta_{n,k}$, going $(k,1,n,2,n-1,\ldots )$ and uniquely defined by

$$ \beta_{n,k}(t)=\left\lbrace\begin{array}{rcl} k & \textrm{if} & t=2j-1, \ j=1 \\ n+2-j & \textrm{if} & t=2j-1, \ 1\lt j\leq n-r+1 \\ n+1-j & \textrm{if} & t=2j-1, \ n-r+1\lt j \\ j & \textrm{if} & t=2j, \ 1\lt j\lt k \\ j+1 & \textrm{if} & t=2j, \ k\leq j \\ \end{array}\right.\tag{2} $$

Let us introduce some more notation. Let $x\in{\mathbb R}$, and $Y$ be a finite set of $m\geq 2$ numbers, $Y=\lbrace y_1 \lt y_2 \lt \ldots \lt y_m \rbrace$, and let $\sigma$ be a permutation of $[|1..m|]$.

Define

$$ \begin{array}{rcl} W'(Y,\sigma) & = & \sum_{j=2}^{m} |y_{\sigma(j)}-y_{\sigma(j+1)}| \\ W^{-}(x,Y,\sigma) & = & -(x-y_{\sigma(1)})+W'(Y,\sigma) \\ W^{+}(x,Y,\sigma) & = & \ (x-y_{\sigma(1)})+W'(Y,\sigma) \\ W(x,Y,\sigma) & = & \ |x-y_{\sigma(1)}|+W'(Y,\sigma)=\max(W^{-}(x,Y,\sigma),W^{+}(x,Y,\sigma)) \end{array}\tag{3} $$

We will also write $\mu_{m}(Y)$ for the "center" of $Y$, namely $\mu_{m}$ is the middle element $y_{p}$ if $m=2p+1$ is odd, and is the mean $\frac{y_{p}+y_{p+1}}{2}$ if $m=2p$ is even.

Then we have :

Main theorem. Consider the problem of maximizing, for fixed $x,m,Y$, the expression $G(\sigma)=W(x,Y,\sigma)$. If $x\leq \mu_{m}(Y)$, then the maximum is attained at $B_m=\beta_{m,m}$ and equals $G(\beta_{m,m})=W^{-}(x,Y,\beta_{m,m})$. We denote this number by $M^{\beta}_m$. If $x\geq \mu_{m}(Y)$, then the maximum is attained at $A_m=\alpha_{m,1}$ and equals $G(\alpha_{m,1})=W^{+}(x,Y,\alpha_{m,1})$. We denote this number by $M^{\alpha}_m$.

Proof of main theorem. We argue by induction on $m\geq 2$. In the base case $m=2$, there are only two permutations, $A_2$ the identity and $B_2$ the transposition that exchanges $1$ and $2$ ; now $W(x,Y,A_2)=|x-y_1|+|y_2-y_1|$ and $W(x,Y,B_2)=|x-y_2|+|y_2-y_1|$ and $\mu_2=\frac{y_1+y_2}{2}$ ; the result is now clear.

Suppose that the result holds for $m-1$, and let us try to show the result for $m$. Let $\sigma$ be an arbitrary permutation of $[|1..m|]$. We must show that $G(\sigma) \leq M^{\beta}_m$ when $y\leq \mu_m(Y)$ and $G(\sigma) \leq M^{\alpha}_m$ when $y\geq \mu_m(Y)$. Let $k=\sigma(1)$ and $Y'=Y\setminus \lbrace y_{k} \rbrace$ ; this has cardinality $m-1$, so we can write it as $Y'=\lbrace y'_1 \lt y'_2 \lt \ldots \lt y'_{m-1} \rbrace$. Then, we can write

$$ \begin{array}{rcl} W(x,Y,\sigma) &=& |x-y_{\sigma(1)}|+\sum_{j=2}^{m}|y_{\sigma(j)}-y_{\sigma(j+1)}| \\ &=& |x-y_{k}|+|y_{k}-y'_{\tau(1)}|+\sum_{j=2}^{m-1}|y'_{\tau(j)}-y'_{\tau(j+1)}| \\ &=& |x-y_{k}|+W(y_{k},Y',\tau), \end{array}\tag{4} $$

where $\tau$ is some permutation of $[|1..(m-1)|]$ which we needn't write out here. By the induction hypothesis,

$$ W(x,Y,\sigma) \leq |x-y_k| + \left\lbrace\begin{array}{rcl} W(y_{k},Y',B_{m-1}) &\textrm{if}& y_k \leq \mu_{m-1}(Y') \\ W(y_{k},Y',A_{m-1}) &\textrm{if}& y_k \geq \mu_{m-1}(Y') \end{array}\right.\tag{5} $$

or in other words,

$$ W(x,Y,\sigma) \leq \left\lbrace\begin{array}{rcl} W(x,Y,\alpha_{m,k}) &\textrm{if}& y_k \leq \mu_{m-1}(Y') \\ W(x,Y,\beta_{m,k}) &\textrm{if}& y_k \geq \mu_{m-1}(Y') \end{array}\right.\tag{6} $$

Supoose first that $k\lt \frac{m+1}{2}$. Then we have both $y_k\leq \mu_{m-1}(Y')$ and $y_k\leq \mu_{m}(Y)$, so we are necessarily in the first case of (6) above, so that $W(x,Y,\sigma) \leq W(x,Y,\alpha_{m,k})$. If $x\leq y_k$, we have

$$ \begin{array}{rcl} M^{\beta}_m-W(x,Y,\alpha_{m,k}) &=& W(x,Y,B_m) - W(x,Y,\alpha_{m,k}) \\ &=& W^{-}(x,Y,B_m) - W^{-}(x,Y,\alpha_{m,k}) \\ &=& 2(\mu_m(Y)-y_k) \geq 0. \end{array}\tag{7} $$

Next, if $y_k \leq x \leq \mu_m(Y)$, we have

$$ \begin{array}{rcl} M^{\beta}_m-W(x,Y,\alpha_{m,k}) &=& W(x,Y,B_m) - W(x,Y,\alpha_{m,k}) \\ &=& W^{-}(x,Y,B_m) - W^{+}(x,Y,\alpha_{m,k}) \\ &=& 2(\mu_m(Y)-x) \geq 0. \end{array}\tag{8} $$

Finally, if $\mu_m(Y) \leq x$, we have

$$ \begin{array}{rcl} M^{\alpha}_m-W(x,Y,\alpha_{m,k}) &=& W(x,Y,A_m) - W(x,Y,\alpha_{m,k}) \\ &=& W^{+}(x,Y,A_m) - W^{+}(x,Y,\alpha_{m,k}) \\ &=& 0. \end{array}\tag{9} $$

This finishes the case $k\lt \frac{m+1}{2}$. The case $k\gt \frac{m+1}{2}$ is symmetric, so we are left with the case $k=\frac{m+1}{2}$, or $m=2k-1$. Then $\mu_{m}(Y)=y_k$ and $\mu_{m-1}(Y')=\frac{y_{k-1}+y_{k+1}}{2}$. Our argument will go by a disjunction of $2\times 2=4$ cases, as we need to consider both the position of $x$ wrt $y_k$ (to know whether our wished upper bound is $M^{\alpha}_m$ or $M^{\beta}_m$) and the position of $y_k$ wrt $\frac{y_{k-1}+y_{k+1}}{2}$ (to know which alternative of (6) holds).

If $x \leq y_k$ and $y_k \leq \frac{y_{k-1}+y_{k+1}}{2}$, then

$$ \begin{array}{rcl} M^{\beta}_m-W(x,Y,\beta_{m,k}) &=& W(x,Y,B_m) - W(x,Y,\beta_{m,k}) \\ &=& W^{-}(x,Y,B_m) - W^{-}(x,Y,\beta_{m,k}) \\ &=& y_{k+1}-y_{k}\geq 0. \end{array}\tag{10} $$

If $x \leq y_k$ and $y_k \geq \frac{y_{k-1}+y_{k+1}}{2}$, then

$$ \begin{array}{rcl} M^{\beta}_m-W(x,Y,\alpha_{m,k}) &=& W(x,Y,B_m) - W(x,Y,\alpha_{m,k}) \\ &=& W^{-}(x,Y,B_m) - W^{-}(x,Y,\alpha_{m,k}) \\ &=& y_k-y_{k-1}\geq 0. \end{array}\tag{11} $$

If $x \geq y_k$ and $y_k \leq \frac{y_{k-1}+y_{k+1}}{2}$, then

$$ \begin{array}{rcl} M^{\alpha}_m-W(x,Y,\beta_{m,k}) &=& W(x,Y,A_m) - W(x,Y,\beta_{m,k}) \\ &=& W^{+}(x,Y,A_m) - W^{+}(x,Y,\beta_{m,k}) \\ &=& y_{k+1}-y_{k}\geq 0. \end{array}\tag{12} $$

If $x \geq y_k$ and $y_k \geq \frac{y_{k-1}+y_{k+1}}{2}$, then

$$ \begin{array}{rcl} M^{\alpha}_m-W(x,Y,\alpha_{m,k}) &=& W(x,Y,A_m) - W(x,Y,\alpha_{m,k}) \\ &=& W^{+}(x,Y,A_m) - W^{+}(x,Y,\alpha_{m,k}) \\ &=& y_{k}-y_{k-1}\geq 0. \end{array}\tag{13} $$

The main theorem is proved.

Corollary (of main theorem). For a finite set $X=\lbrace x_1 \lt x_2 \lt \ldots \lt x_n \rbrace$ and a permutation $\sigma$ of $[|1..n|]$, let $F(\sigma)=\sum_{j=1}^{n}|x_{\sigma(j)}-x_{\sigma(j-1)}|$.

Let $\Sigma_n$ be the set of the permutations defined by

$$ \Sigma_n= \bigg\lbrace \alpha_{n,j} \ \bigg| \ 1 \leq j \leq \frac{n+1}{2} \bigg\rbrace \bigcup \bigg\lbrace \beta_{n,j} \ \bigg| \ \frac{n+1}{2} \leq j \leq n \bigg\rbrace \tag{14} $$

(where $\alpha$ and $\beta$ are defined by (1) and (2) ; thus $\Sigma_n$ containes $n$ elements when $n$ is even and $n+1$ elements when $n$ is odd). Then the maximum of $F$ is attained at least once on $\Sigma_n$.

For example, when $n=4$, you only need to consider the permutations $(1,4,2,3)$, $(2,4,1,3)$, $(3,1,4,2)$ and $(4,1,3,2)$.