Dado un tubo con bolas numeradas (al azar). El tubo tiene agujeros para quitar una pelota. Considere los siguientes pasos para una operación:
- Puede elegir una o más bolas de los agujeros y recordar el orden en que las recogió.
- Debe inclinar la tubería hacia el lado izquierdo para que las bolas restantes en la tubería se muevan hacia la izquierda y ocupen el espacio vacío creado al quitar las bolas.
- Se supone que no debe cambiar el orden en el que recogió las bolas numeradas de la tubería. Ahora los vuelve a colocar en la tubería utilizando el espacio vacante creado por el movimiento de las bolas.
Los pasos 1 a 3 se consideran una sola operación.
Descubra las operaciones mínimas requeridas para ordenar las bolas numeradas en orden ascendente.
Por ejemplo: si el tubo contiene:[ 1 4 2 3 5 6 ]
Luego podemos sacar y y , y si inclinamos la tubería hacia la izquierda, obtenemos , e insertamos en ese orden hasta el final de la tubería para obtener .4 5 6 [ 1 2 3 ] ( 4 5 6 ) [ 1 2 3 4 5 6 ]
Entonces, el número mínimo de pasos necesarios es 1. Necesito encontrar operaciones mínimas para ordenar la tubería.
¿Alguna idea o sugerencia sobre cómo resolver este problema?
fuente
Respuestas:
Defina el número de partición de ejecución de una permutación π , denotado r ( π ) , utilizando el siguiente proceso. Sea k el número entero máximo de tal manera que los números min ( π ) , ... , k aparezcan en orden creciente en . Elimínelos de y repita el proceso. El número de rondas necesarias para consumir toda la permutación es .π r(π) k min(π),…,k π π r ( π )π π r(π)
Por ejemplo, calculemos . Primero reservamos , para obtener . Luego dejamos de lado , para obtener . Luego dejamos de lado , para obtener . Finalmente, dejamos de lado para obtener la permutación vacía. Esto toma cuatro rondas, entonces .r ( 62735814 ) 1 6273584 234 6758 5 678 678 r ( 62735814 ) = 4r(62735814) 1 6273584 234 6758 5 678 678 r(62735814)=4
¿Cómo es útil esta representación para ordenar ? Tome cada segundo recorrido, es decir, , y mueva estos números a la derecha para obtener (editar: en el orden en que aparecen en la permutación, es decir, ). Ahora solo hay dos ejecuciones, a saber , y podemos ordenar la lista moviendo a la derecha.62735814 234 , 678 51627384 627384 1234 , 5678 567862735814 234,678 51627384 627384 1234,5678 5678
Ahora permítame hacer la siguiente conjetura: para una permutación π , deje Π ser el conjunto de todas las permutaciones a las que se puede acceder desde π en un solo movimiento. Entonces min α ∈ Π r ( α ) = ⌈ r ( π ) / 2 ⌉ .π Π π minα∈Πr(α)=⌈r(π)/2⌉
Dada esta conjetura, es fácil mostrar que el número mínimo de movimientos necesarios para ordenar una permutación π es ⌈ log 2 r ( π ) ⌉ , y he verificado esta fórmula para todas las permutaciones en S n para n ≤ 8 .π ⌈log2r(π)⌉ Sn n≤8
Editar: Aquí hay una interpretación diferente del número de partición de ejecución que proporciona un algoritmo de tiempo lineal para calcularlo y me permite esbozar una prueba de mi conjetura, verificando así la fórmula ⌈ log 2 r ( π ) ⌉ .⌈log2r(π)⌉
Considere la permutación 62735814 nuevamente. La razón por la que la primera ejecución termina en 1 es que 2 aparece antes que 1 . Del mismo modo, la segunda ejecución termina en 4 ya que 5 aparece antes que 4 , y así sucesivamente. Por lo tanto, el número de partición de ejecución de una permutación es el número de i s tal que i + 1 aparece antes que i .62735814 1 2 1 4 5 4 i i+1 i
Podemos afirmar esto de manera más sucinta si observamos el inverso de la permutación. Considere nuevamente π = 62735814 . Tome π - 1 = 72485136 . Esta permutación tiene tres descensos: 7 2 48 5 1 36 (un descenso es una posición más pequeña que la anterior). Cada uno de los descensos corresponde al inicio de una nueva carrera. Entonces r ( π ) es igual a uno más el número de descensos en π - 1 .π=62735814 π−1=72485136 72485136 r(π) π−1
¿Cómo se ve la operación en términos de π - 1 ? dejemos que B sea el conjunto de números que nos movemos hacia la derecha, y A sea el conjunto de números que permanecen a la izquierda. Reemplazamos los números en A con una permutación en { 1 , … , | A | } representando su orden relativo, y reemplaza los números en B con una permutación en { | A | + 1 , ... , | A | + | B | }π−1 B A A {1,…,|A|} B {|A|+1,…,|A|+|B|} . Por ejemplo, considere el movimiento 6273 5 8 1 4 ↦ 51 627384 . En términos de permutaciones inversas, es 7 248 5 136 ↦ 2 468 1 357 . Entonces 75 se asignó a 21 y 248136 se asignó a 468357 .62735814↦51627384 72485136↦24681357 75 21 248136 468357
Un descenso ... x y ... en π - 1 se pierde después de la operación sólo si x ∈ A y y ∈ B . Por el contrario, en términos de π - 1 , la partición en A y B corresponde a A -runs y B -runs; cada vez que finaliza una carrera B y comienza una carrera A , hay un descenso. Para "matar" un descenso, tenemos que cambiar de una carrera A a una B…xy… π−1 x∈A y∈B π−1 A B A B B A A B -correr. Si matamos dos descensos, habremos cambiado en el medio de una ejecución B a una ejecución A , incurriendo en un descenso.B A
Este argumento puede formalizarse para mostrar que si α surge de π a través de una operación, entonces d ( α - 1 ) ≥ ⌊ d ( π - 1 ) / 2 ⌋ , donde d ( ⋅ ) es el número de descensos. Esto es equivalente a r ( α ) ≥ ⌈ r ( π ) / 2 ⌉α π d(α−1)≥⌊d(π−1)/2⌋ d(⋅) r(α)≥⌈r(π)/2⌉ , demostrando así una dirección de mi conjetura. La otra dirección es más fácil y ya se describió anteriormente: simplemente tomamos cada segundo recorrido y empujamos estos recorridos hacia la derecha para obtener una permutación α satisfactoria r ( α ) = ⌈ r ( π / 2 ) ⌉ .α r(α)=⌈r(π/2)⌉
fuente