Problema interesante en la clasificación

14

Dado un tubo con bolas numeradas (al azar). El tubo tiene agujeros para quitar una pelota. Considere los siguientes pasos para una operación:

  1. Puede elegir una o más bolas de los agujeros y recordar el orden en que las recogió.
  2. 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.
  3. 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 ]     [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 ]456  [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?

Rakesh
fuente
Si vienen en el orden inverso, debe sacar 2, 3, ... en orden y agregar al final, para nn operaciones en total. Este es claramente el peor de los casos.
vonbrand
2
8,7,6,5,4,3,2,1 -> 75318642 -> 51627384 -> 12345678 sacando siempre las posiciones impares.
adrianN
Resumiendo mi respuesta: el número mínimo de operaciones requeridas para ordenar una permutación π es log 2 ( d ( π - 1 ) + 1 ) , donde es el número de descensos. πlog2(d(π1)+1)d ( )d()
Yuval Filmus
Me gusta pensar en términos de eliminar inversiones. Con cada operación, puede eliminar las inversiones entre cualquier conjunto y (donde es el conjunto completo de bolas). Entonces, solo tienes que elegir tus sets cuidado. X S - X S XXSXSX
Joe

Respuestas:

10

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(π)kmin(π),,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)1627358423467585678678r(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 567862735814234,678516273846273841234,56785678

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(π)Snn8

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 .62735814121454ii+1i

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=7248513672485136r(π)π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 | }π1BAA{1,,|A|}B{|A|+1,,|A|+|B|}. Por ejemplo, considere el movimiento 6273 5 8 1 451 627384 . En términos de permutaciones inversas, es 7 248 5 1362 468 1 357 . Entonces 75 se asignó a 21 y 248136 se asignó a 468357 .627358145162738472485136246813577521248136468357

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 Bxyπ1xAyBπ1ABABBAAB-correr. Si matamos dos descensos, habremos cambiado en el medio de una ejecución B a una ejecución A , incurriendo en un descenso.BA

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)/2d()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)

Yuval Filmus
fuente
Estás sacando varias rondas de bolas a la vez, entiendo que no está permitido.
vonbrand
1
Los estoy tomando en el orden en que aparecen en la permutación . Eso es legal
Yuval Filmus
Estoy un poco confundido. ¿puede explicar el número mínimo de operaciones requeridas para ordenar [6 5 4 3 2 1] y también mencionó como "Tome cada segundo recorrido, es decir, 234,678, y mueva estos números a la derecha para obtener 51627384" puede explicar esto con detalle y también cómo calcular r (π) de manera eficiente?
user6709
1) r ( 654321 ) = 6 , por lo que necesitaría 3 operaciones. Por ejemplo, 654321 531 | 642 51 | 6234 1234 | 56 .
Yuval Filmus
2) Toma todos los números que pertenecen a estas corridas (en el orden en que aparecen en la permutación) y los mueve hacia la derecha. En este caso, toma 627384 y los mueve hacia la derecha, dejando 51 a la izquierda.
Yuval Filmus