Least permutations needed to permute from decreasing order to increasing order

Solution 1:

I don’t know that it’s best possible, but I can show that if $T(n)$ swaps are needed to reverse $\langle n,n-1,\ldots,1\rangle$, then $T(n)\le\left\lfloor\frac{3n}4\right\rfloor$. For convenience let $f(n)=\left\lfloor\frac{3n}4\right\rfloor$. It’s not hard to verify that $T(1)=0=f(1)$, $T(2)=1=f(2)$, $T(3)=2=f(3)$, and $T(4)=3=f(4)$, and the OP has shown that $T(5)=3=f(5)$.

Now suppose that $n>5$, and $T(k)\le f(k)$ for $k<n$. Let $n=4q+r$, where $r\in\{0,1,2,3\}$ and $q\ge 1$. In $3$ swaps the initial sequence can be transformed into

$$\sigma=\langle n-4,n-3,n-2,n-1,n,n-5,n-6,\ldots,2,1\rangle\;.$$

Now treat the first $5$ terms of $\sigma$ as a single entity $\widehat{n-4}$ and work with the sequence

$$\hat\sigma=\left\langle\widehat{n-4},n-5,n-6,\ldots,2,1\right\rangle$$

of length $n-4=4(q-1)+r$. The induction hypothesis says that

$$T(n-4)\le f(n-4)=3(q-1)+f(r)\;,$$

so $\hat\sigma$ can be transformed into

$$\left\langle 1,2,\ldots,n-5,\widehat{n-4}\right\rangle=\langle 1,2,\ldots,n-5,n-4,n-3,n-2,n-1,n\rangle$$

with $3(q-1)+f(r)$ further switches. Thus,

$$T(n)\le 3+3(q-1)+f(r)=3q+f(r)=f(n)\;,$$

and the induction is complete.

Added: This can definitely be improved. For a string $\langle a_1,\ldots,a_n\rangle$ and $1\le i<j\le k\le n$ let $S(i,j,k)$ be the operation of swapping the substrings $\langle a_i,\ldots,a_{j-1}\rangle$ and $\langle a_j,\ldots,a_k\rangle$. If $n=2m+1$, perform the swaps $S(k,k+2,k+m+1)$ for $k=m,m-1,\ldots,1$, then perform $S(2,m+1,n)$. Then:

• $a_n=1$ moves $2$ places to the left $m$ times, putting it in position $1$ where it stays on the last move;
• $a_{n-1}=2$ moves $2$ places to the left $m-1$ times, reaching position $2$, then $S(2,4,m+3)$ moves it to position $m+2$, and the final swap moves it back to position $2$;
• in general for $k=0,\ldots,m-1$, $a_{n-k}=k+1$ moves $2$ places to the left $m-k$ times to reach position $k+1$, then moves to position $m+k+1$ with $S(k+1,k+3,m+k+2)$, where it remains until the final swap moves it back to position $k+1$;
• $a_{m+1}=m+1$ is sent by the first swap to position $n$, where it stays until the final swap moves it back to its original position;
• for $k=2,\ldots,m$, $a_k=n+1-k$ stays in its original position for the first $m-k$ swaps, at which point it moves $m$ places to the right to position $m+k$, after which it moves left $2$ places with each of the remaining $k-1$ swaps before the final one, reaching position $m-k+2$, and the final swap takes it to position $2m-k+2=n+1-k$; and
• $a_1=n$ stays in its original position for the first $m-1$ swaps, then moves to position $m+1$ and thence to position $2m+1=n$ with the final two swaps.

Thus, $T(2n+1)\le m+1$.

It’s not hard to check that if $n=2m$, the swaps $S(k,k+2,k+m+1)$ for $k=m-1,\ldots,1$ followed by $S(1,2,2)$ and $S(3,m+2,2m)$ will convert $\langle 2m,\ldots,1\rangle$ to $\langle 1,\ldots,2m\rangle$, so $T(2m)\le m+1$, and in general we have

$$T(n)\le\left\lceil\frac{n+1}2\right\rceil\;.$$

Solution 2:

You need at least $\lceil (n+1)/2\rceil.$ Consider the number $G$ of terms whose right neighbor is greater. $G$ starts at zero and ends as $n-1.$

For example $$G(5,4,3,2,1)=0$$ $$G(5,2,1\color{red},4,3)=1$$ $$G(1\color{red},4\color{red},5,2\color{red},3)=3$$ $$G(1\color{red},2\color{red},3\color{red},4\color{red},5)=4$$ I have colored in red the comma between each term and its right neighbour whenever that neighbour is greater.

By Brian M. Scott's definition given in the comments, each swap is of the form $WXYZ\to WYXZ$ where $W,X,Y,Z$ are possibly empty subwords. Let $q,r,s,t$ be the lengths of $W,X,Y,Z$ respectively. Let

$$w_1,\dots,w_q,x_1,\dots,x_r,y_1,\dots,y_s,z_1,\dots,z_t=WXYZ$$ so $$w_1,\dots,w_q,y_1,\dots,y_s,x_1,\dots,x_r,z_1,\dots,z_t=WYXZ.$$

For example for $5,4,3,2,1\to 5,2,1,4,3$ we have $(q,r,s,t)=(1,2,2,0).$ Note \begin{align*} G(WYXZ)-G(WXYZ)=[w_q<y_1]+[y_s<x_1]+[x_r<z_1]\\-[w_q<x_1]-[x_r<y_1]-[y_s<z_1]\tag{1} \end{align*} where $[a<b]=1$ if $a<b$ and $[a<b]=0$ otherwise (Iverson bracket notation). If $q=0$ ignore the terms using $w_q,$ and if $t=0$ ignore the terms using $z_1.$ We can write the entire sequence of swaps as $P_0\to P_1\to \dots\to P_m$ where $m$ is the number of swaps, and $P_0=(n,n-1,\dots,1),$ and $P_m=(1,2,\dots,n).$

In the first swap $WXYZ=P_0\to P_1=WYXZ,$ we always have $w_q>y_1$ and $x_r>z_1.$ So by (1) we must have $G(P_1)-G(P_0)\leq 1.$ In the final swap $WXYZ=P_{m-1}\to P_m=WYXZ$ we always have $w_q<x_1$ and $y_s<z_1,$ so $G(P_m)-G(P_{m-1})\leq 1.$ Now consider an arbitrary swap $WXYZ=P_{i}\to P_{i+1}=WYXZ.$ From (1) we know $G(P_{i+1})-G(P_i)\leq 3,$ and it cannot be exactly $3$ because that would give $w_q<y_1<x_r<z_1<y_s<x_1<w_q.$ So $G(P_{i+1})-G(P_i)\leq 2.$ To summarize:

\begin{align*} &G(P_{1})&-&&&G(P_0)&\leq 1\\ &G(P_{i+1})&-&&&G(P_i)&\leq 2&\qquad\text{ for }1\leq i\leq m-2\\ &G(P_{m})&-&&&G(P_{m-1})&\leq 1 \end{align*}

which sum to $n-1=G(P_m)-G(P_0)\leq 2m-2.$ So $m\geq\lceil (n+1)/2\rceil.$

Solution 3:

$n-1$ is an upper bound as we can exhibit an algorithm that achieves that. Take successive pairs of elements and invert them. This uses $\lfloor \frac n2 \rfloor$ swaps. Lock together the pairs you have swapped, considering the pair to be one element, and you have $n-\lfloor \frac n2 \rfloor=\lceil \frac n2 \rceil$ elements left. Now use the same algorithm again. Repeat until you have only one element left, which means the list is in proper order.

Let $T(n)$ be the number of swaps needed for a list of length $n$. $T(1)=0, T(2)=1$ are the base cases for induction. Assume $T(k)=k-1$ has been proven up to $k$. Then $T(k+1)=\lfloor \frac {k+1}2 \rfloor + T(\lceil \frac {k+1}2 \rceil)=\lfloor \frac {k+1}2 \rfloor + \lceil \frac {k+1}2 \rceil-1=k$