Least permutations needed to permute from decreasing order to increasing order

Question

You are asked to permute the neighboring sub-sequence of the sequence $n,n-1,n-2,\cdots,1$ until the sequence is brought to the increasing order.

By permute the neighboring sub-sequence I mean for example: $5,4,3,2,1 \to 5,3,4,2,1 $ or $5,4,3,2,1\to 5,2,4,3,1$ or $5,4,3,2,1\to5,2,1,4,3$.

What is the least number of permutations needed?

Edit

A first nontrivial case I can come up with is:

$$ 54321\to52143\to14523\to12345 $$

Edit 2

A second nontrivial case I come up with to show $T(n)<f(n)$ is possible regarding the answer by @Brian M. Scott: $$ 7654321\to7632154\to7215634\to1567234\to1234567 $$ maybe $\frac{n+1}{2}$?

Answer 1

$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$

Answer 2

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\;.$$