¿Cómo detectar el orden de la pila?

Tomamos la secuencia de enteros de $1$ a $n$, y los empujamos a una pila uno por uno en orden. Entre cada inserción, podemos elegir hacer estallar cualquier cantidad de elementos de la pila (desde 0 hasta el tamaño actual de la pila).

Cada vez que saquemos un valor de la pila, lo imprimiremos.

Por ejemplo, $1,2,3$se imprime cuando lo hacemos push, pop, push, pop, push, pop.$3,2,1$proviene de push, push, push, pop, pop, pop.

Sin embargo, $3,1,2$ no es una impresión posible, porque no es posible tener $3$ impreso seguido de $1$, sin ver $2$ entre.

Pregunta: ¿Cómo podemos detectar órdenes imposibles como$3,1,2$?

De hecho, según mi observación, he encontrado una solución potencial. Pero el problema es que no puedo probar que mi observación esté completa.

El programa que escribí con la siguiente lógica:

Cuando el valor actual menos el siguiente valor es mayor que 1, un valor entre actual y siguiente no puede aparecer después del siguiente. Por ejemplo, si current = 3 y next = 1, entonces el valor entre current (3) y next (1) es 2 que no puede aparecer después de next (1), por lo tanto$3,1,2$ viola la regla

¿Esto cubre todos los casos?

No pude entender su enfoque exactamente (Parece que es correcto), pero hay una regla simple para órdenes imposibles: la orden es imposible $iff$ Ahi esta $a_i,a_j,a_k$ tal que $a_i > a_k > a_j$ y $i<j<k$. A tal$a_i,a_j,a_k$ decimos mal triple.

¿Por qué? Primero debes demostrar que si hay un triple malo, entonces la secuencia es imposible, pero esto es simple y lo dejaré como ejercicio (el número del medio no podría aparecer antes que el más grande, excepto los más pequeños antes de todos).

En segundo lugar, debe demostrar que todas las órdenes imposibles tienen al menos un triple malo, suponga que tiene una secuencia sin ningún triple malo, puede encontrar el orden de empujar y explotar, por lo que no es una secuencia imposible. Para reconstruir las órdenes push y pop solo use un enfoque ingenuo (la operación es pop mientras itera sobre números consecutivos), pero para una prueba formal (por simplicidad) podría usar la inducción, suponga para todas las secuencias de longitud$m$Si no hay un triple malo, no son imposibles. Para secuencia de longitud$n$, puede establecer operaciones como pop (comenzar desde el final de la secuencia), mientras se encuentra con números consecutivos crecientes, ahora tiene una secuencia de longitud $m$, con $m < n$, sin triples malos, por lo que puede reconstruir push and pop para esta secuencia, por lo que el original no era imposible. El inicio de la inducción es una secuencia de longitud 3.