Clasificación de panqueques

La clasificación de panqueques es el problema matemático de ordenar una pila desordenada de panqueques por tamaño cuando se puede insertar una espátula en cualquier punto de la pila y usarla para voltear todos los panqueques que están encima. Un número de panqueques es el número mínimo de volteos necesarios para una cantidad dada de panqueques. En esta forma, el problema fue analizado por primera vez por el geómetra estadounidense Jacob E. Goodman . ^{[ 1 ]} Una variante del problema se refiere a panqueques quemados , donde cada panqueque tiene un lado quemado y todos los panqueques deben, además, terminar con el lado quemado hacia abajo.

Todos los métodos de ordenación requieren la comparación de pares de elementos. En el problema de ordenación tradicional , el objetivo habitual es minimizar el número de comparaciones necesarias para ordenar una lista . El número de operaciones reales, como intercambiar dos elementos, resulta irrelevante. En cambio, en los problemas de ordenación de tipo "panqueque", el objetivo es minimizar el número de operaciones, donde las únicas operaciones permitidas son la inversión de los elementos de un prefijo determinado de la secuencia. En este caso, el número de comparaciones también resulta irrelevante.

La discusión anterior presupone que cada panqueque es único, es decir, la secuencia en la que se realizan las inversiones de prefijo es una permutación . Sin embargo, las "cadenas" son secuencias en las que un símbolo puede repetirse, y esta repetición puede reducir el número de inversiones de prefijo necesarias para ordenar. Chitturi y Sudborough (2010) y Hurkens et al. (2007) demostraron independientemente que la complejidad de transformar una cadena compatible en otra con el número mínimo de inversiones de prefijo es NP-completa . También dieron cotas para la misma. Hurkens et al. dieron un algoritmo exacto para ordenar cadenas binarias y ternarias. Chitturi ^{[ 8 ]} (2011) demostró que la complejidad de transformar una cadena con signo compatible en otra con el número mínimo de inversiones de prefijo con signo —el problema del panqueque quemado en cadenas— es NP-completa.

El problema de la clasificación de panqueques fue planteado por primera vez por Jacob E. Goodman , quien escribía bajo el seudónimo de "Harry Dweighter" ("camarero apurado"). ^{[ 9 ]}

Aunque se ve más a menudo como un dispositivo educativo, la clasificación de panqueques también aparece en aplicaciones en redes de procesadores paralelos, en las que puede proporcionar un algoritmo de enrutamiento eficaz entre procesadores. ^{[ 10 ] [ 11 ]}

El problema es notable por ser el tema del único artículo matemático conocido del fundador de Microsoft , Bill Gates (como William Gates), titulado "Bounds for Sorting by Prefix Reversal" y escrito en coautoría con Christos Papadimitriou . Publicado en 1979, describe un algoritmo eficiente para la ordenación de panqueques. ^{[ 3 ]} Además, el artículo más notable publicado por el cocreador de Futurama, David X. Cohen (como David S. Cohen), escrito en coautoría con Manuel Blum , trataba sobre el problema del panqueque quemado. ^{[ 12 ]}

Los problemas relacionados de ordenación por inversión de signos y ordenación por inversión también se han estudiado más recientemente. Si bien se han encontrado algoritmos exactos eficientes para la ordenación por inversión de signos, ^{[ 13 ]} se ha demostrado que el problema de la ordenación por inversión es difícil incluso de aproximar con un cierto factor constante, ^{[ 14 ]} y también se ha demostrado que es aproximable en tiempo polinomial con un factor de aproximación de 1,375. ^{[ 15 ]}

Un grafo n -panqueque es un grafo cuyos vértices son las permutaciones de n símbolos del 1 al n y cuyas aristas están dadas entre permutaciones transitivas mediante inversiones de prefijos. Es un grafo regular con n! vértices y su grado es n − 1. El problema de ordenar panqueques y el problema de obtener el diámetro del grafo panqueque son equivalentes. ^{[ 16 ]}

El grafo panqueque de dimensión n , P _n, se puede construir recursivamente a partir de n copias de P _{n − 1} , asignando un elemento diferente del conjunto {1, 2, …, n} como sufijo a cada copia.

Su circunferencia :

${\displaystyle g(P_{n})=6{\text{, si }}n>2}$.

El género γ (P _n ) de P _n es: ^{[ 17 ]}

${\displaystyle n!\left({\frac {n-4}{6}}\right)+1\leq \gamma (P_{n})\leq n!\left({\frac {n-3}{4}}\right)-{\frac {n}{2}}+1}$

Dado que los grafos panqueque poseen muchas propiedades interesantes, como estructuras simétricas y recursivas, grados y diámetros pequeños en comparación con el tamaño del grafo, se les presta mucha atención como modelo de redes de interconexión para computadoras paralelas. ^{[ 18 ] [ 19 ] [ 20 ]} Cuando consideramos los grafos panqueque como modelo de redes de interconexión, el diámetro del grafo es una medida que representa el retardo de la comunicación. ^{[ 21 ] [ 22 ]}

Los grafos de panqueques son grafos de Cayley (por lo tanto, son transitivos en vértices ) y resultan especialmente atractivos para el procesamiento paralelo. Tienen grado y diámetro sublogarítmicos y son relativamente dispersos (en comparación con, por ejemplo, los hipercubos ). ^{[ 17 ]}

A continuación se muestra un ejemplo del algoritmo de ordenación de panqueques en Python . El código es similar al de la ordenación de burbuja o la ordenación por selección .

def flip ( arr , k : int ) -> None :izquierda = 0mientras izquierda < k :arr [ izquierda ], arr [ k ] = arr [ k ], arr [ izquierda ]k -= 1izquierda += 1def max_index ( arr , k : int ) -> int :índice = 0para i en rango ( k ):si arr [ i ] > arr [ índice ]:índice = iíndice de retornodef pancake_sort ( arr ) -> None :n = len ( arr )mientras n > 1 :maxidx = max_index ( arr , n )Si maxidx != n - 1 :Si maxidx != 0 :voltear ( arr , maxidx )voltear ( arr , n - 1 )n -= 1arr = [ 15 , 8 , 9 , 1 , 78 , 30 , 69 , 4 , 10 ]ordenación_panqueque ( arr )imprimir ( arr )

Secuencias de la Enciclopedia en línea de secuencias de números enteros :

• OEIS : A058986  – número máximo de giros
• OEIS : A067607  – número de pilas que requieren el número máximo de giros (arriba)
• OEIS : A078941  – número máximo de giros para una pila "quemada"
• OEIS : A078942  – el número de volteos para una pila ordenada con el lado quemado hacia arriba.
• OEIS : A092113  – el triángulo anterior, leído por filas

• El rompecabezas de voltear panqueques , que incluye un applet de Java para el problema de los panqueques y un breve análisis.
• "Los problemas de los panqueques" de Douglas B. West
• Weisstein, Eric W. "Clasificación de panqueques" . MathWorld .