Intercambio de subsecuencias consecutivos para invertir $1,2,3,\ldots,n$

Question

Aquí es un problema que he encontrado en Google Plus.

Dada una secuencia $1,2,....,n$ se le permite el intercambio de cualquiera de dos días consecutivos de subsecuencias. Encontrar el menor número de pasos en los que se puede llegar a $n,n-1,.....,1$ el uso de esta transformación. Consecutivos subsecuencias significa que el último elemento de la primera larga es menor que el primer elemento de la segunda larga.

Ejemplos: $$12345 \to 34125 \to 32541 \to 54321$$ Por eso, $T(5)=3$. Algún otro ejemplo son: $T(15)=11, T(13)=9, T(10)=7$

Se ha encontrado que, la transformación puede llevarse a cabo en la mayoría de los $n-1$ maneras, comenzando con el $1,2,\ldots,n-1,n\to n,1,2...,n-1$ y, a continuación, el uso de la inducción. Existe una sencilla fórmula o método para encontrar el menor número de maneras en lugar de la fuerza bruta?

Answer 1

Esto podría no ser la óptima, pero aquí es una mejor obligado.

Comenzando con $1,2,\ldots,n$ intercambio $ 1,2,\ldots,a,b,\ldots,n \rightarrow b,\ldots,n,1,\ldots\,un $ entonces la inversa de cada una de las $[b\ldots n]$ $[1\ldots a]$ en la forma óptima. Si podemos hacer cada parte en $T(k)\le rk-1$ algunos $r<1$ $$ T(n) \le 1+T(n-a)+T(a) \le 1+r(n-a)-1+ra-1 = rn-1 $$ Desde $T(5)=(4/5)\times 5-1$ podemos enlazado $T(5k)\le 4k-1$ todos los $k\ge 1$, y desde $T$ debe ser no decreciente, $T(n)\le 4\lceil\frac{n}{5}\rceil-1$ todos los $n>0$. (Esto puede ser hecho un poco mejor por resolver directamente por $T(6),T(7),T(8),T(9)$.)

Dada una permutación de llamar a un par ordenado de entradas consecutivos $(a,b)$ hacia arriba si $a<b$. Si queremos transformar una secuencia general $$x_1,x_2,\ldots,x_i,y_1,\ldots\,y_j,z_1,\ldots,z_k,w_1,\ldots,w_l$$ por un intercambio de $$x_1,x_2,\ldots,x_i,z_1,\ldots,z_k,y_1,\ldots\,y_j,w_1,\ldots,w_l$$ a continuación, el número de arriba pares puede disminuir en la mayoría de los 2, solo si dos de $z_1<x_i<y_1$, $y_1<z_k<w_1$ y $w_1<y_j<z_1$ son verdaderas (los tres no pueden ser simultáneamente verdaderas). Desde la secuencia inicial $1,2,\ldots,n$ $n-1$ hacia arriba, los pares y la secuencia final debe tener cero, $T(n)\ge \lceil \frac{n-1}{2}\rceil$.

Por lo $\lceil \frac{n-1}{2}\rceil \le T(n) < 4\lceil\frac{n}{5}\rceil$ todos los $n>0$.