algoritmo de montón

El algoritmo de Heap genera todas las permutaciones posibles de $n$ objetos. Fue propuesto por primera vez por BR Heap en 1963. ^[1] El algoritmo minimiza el movimiento: genera cada permutación a partir de la anterior intercambiando un solo par de elementos; los otros $n -2$ elementos no se alteran. En una revisión de 1977 sobre los algoritmos de generación de permutaciones, Robert Sedgewick concluyó que en ese momento era el algoritmo más eficaz para generar permutaciones por computadora. ^[2]

La secuencia de permutaciones de $n$ objetos generada por el algoritmo de Heap es el comienzo de la secuencia de permutaciones de $n +1$ objetos. Entonces hay una secuencia infinita de permutaciones generadas por el algoritmo de Heap (secuencia A280318 en OEIS ).

Detalles del algoritmo

Para una colección que contiene $n$ elementos diferentes, Heap encontró un método sistemático para elegir en cada paso un par de elementos para cambiar con el fin de producir cada permutación posible de estos elementos exactamente una vez. $C$

Descrito recursivamente como un método de disminuir y conquistar , el algoritmo de Heap opera en cada paso de los elementos iniciales de la colección. Inicialmente y posteriormente . Cada paso genera las permutaciones que terminan con los mismos elementos finales. Lo hace llamándose a sí mismo una vez con el elemento inalterado y luego veces con el elemento () intercambiado por cada uno de los elementos iniciales. Las llamadas recursivas modifican los elementos iniciales y se necesita una regla en cada iteración para seleccionar cuáles se intercambiarán con la última. El método de Heap dice que esta elección se puede realizar mediante la paridad del número de elementos operados en este paso. Si es par, entonces el elemento final se intercambia iterativamente con el índice de cada elemento. Si es impar, el elemento final siempre se intercambia con el primero. $k$ $k=n$ $k<n$ $k!$ $nk$ $k{\text{th}}$ $k-1$ $k{\text{th}}$ $k-1$ $k-1$ $k$ $k$

procedimiento generar ( k : entero , A : matriz de cualquiera ) : si k = 1 , entonces salida ( A ) else // Generar permutaciones con k-ésimo inalterado // Inicialmente k = longitud(A) generar ( k - 1 , A )                      // Genera permutaciones para k-ésimo intercambiado con cada k-1 inicial para i := 0 ; yo < k - 1 ; i += 1 do // Intercambiar elección dependiendo de la paridad de k (par o impar) si k es par, entonces intercambiar ( A [ i ] , A [ k - 1 ]) // indexado a cero, el k-ésimo está en k-1 else intercambiar ( A [ 0 ] , A [ k - 1 ] ) terminar si generar ( k - 1 , A ) terminar por terminar si

También se puede escribir el algoritmo en un formato no recursivo. ^[3]

procedimiento generar ( n : entero , A : matriz de cualquiera ) : // c es una codificación del estado de la pila. c[k] codifica el contador de bucle for para cuando se llama a generate(k - 1, A) c : matriz de int               para yo : = 0 ; yo < norte ; i += 1 hacer c [ i ] := 0 finalizar para                salida ( A ) // i actúa de manera similar a un puntero de pila i := 1 ; mientras que i < n haga si c [ i ] < i entonces si i es par entonces intercambie ( A [ 0 ] , A [ i ]) de lo contrario intercambie ( A [ c [ i ]] , A [ i ]) finalice si la salida ( A ) // Se ha producido un intercambio que finaliza el bucle for. Simular el incremento del contador de bucle for c [ i ] += 1 // Simular una llamada recursiva que alcanza el caso base llevando el puntero al caso base analógico en la matriz i := 1 else // Llamando a generate(i+1 , A) ha finalizado cuando finalizó el bucle for. Restablezca el estado y simule hacer estallar la pila incrementando el puntero. c [ i ] := 0 i += 1 final si finaliza mientras

Prueba

En esta prueba, usaremos la implementación siguiente como algoritmo de Heap. Si bien no es óptima (no minimiza los movimientos, como se describe en la sección siguiente), la implementación sigue siendo correcta y producirá todas las permutaciones. La razón para utilizar la siguiente implementación es que el análisis es más fácil y ciertos patrones se pueden ilustrar fácilmente.

procedimiento generar ( k : entero , A : matriz de cualquiera ) : si k = 1, entonces genera ( A ) en caso contrario para i : = 0 ; yo < k ; i += 1 genera ( k - 1 , A ) si k es par, entonces intercambia ( A [ i ] , A [ k - 1 ]) de lo contrario intercambia ( A [ 0 ] , A [ k - 1 ]) finaliza si                                           fin por fin si

Reclamación: Si la matriz $A$ tiene una longitud $n$ , entonces la ejecución del algoritmo de Heap dará como resultado que $A$ se "gire" hacia la derecha en 1 (es decir, cada elemento se desplaza hacia la derecha con el último elemento ocupando la primera posición) o que $A$ sea inalterado, dependiendo de si $n$ es par o impar, respectivamente.

Base: La afirmación anterior es trivialmente válida ya que el algoritmo de Heap simplemente devolverá $A$ inalterado en orden. $n=1$

Inducción: Suponga que la afirmación es cierta para algunos . Entonces necesitaremos manejar dos casos para que : sea par o impar. $i\geq 1$ $i+1$ $i+1$

Si, para $A$ , es par, entonces el subconjunto de los primeros $i$ elementos permanecerá inalterado después de realizar el algoritmo de Heap en el subconjunto, como se supone en la hipótesis de inducción. Al realizar el algoritmo de Heap en el subarreglo y luego realizar la operación de intercambio, en la $k$ -ésima iteración del bucle for, donde , el $k$ -ésimo elemento en $A$ se intercambiará a la última posición de $A$ , que puede considerarse como una especie de "buffer". Al intercambiar el primer y el último elemento, luego intercambiar el segundo y el último, hasta que se intercambien el $enésimo$ y el último elemento, la matriz finalmente experimentará una rotación. Para ilustrar lo anterior, vea a continuación el caso $n=i+1$ $k\leq i+1$ $n=4$

1,2,3,4... Matriz original1,2,3,4... 1.ª iteración (permutar subconjunto)4,2,3,1 ... 1.ª iteración (intercambiar el 1.er elemento en "búfer")4,2,3,1... 2da iteración (Permutar subconjunto)4,1,3,2 ... 2.ª iteración (intercambiar el 2.º elemento en "búfer")4,1,3,2... 3.ª iteración (permutar subconjunto)4,1,2,3 ... 3.ª iteración (intercambiar el 3.er elemento en "búfer")4,1,2,3... 4ta iteración (Permutar subconjunto)4,1,2,3... 4.ª iteración (intercambiar el 4.º elemento en un "búfer")... La matriz alterada es una versión rotada del original.

Si, para $A$ , es impar, entonces el subconjunto de los primeros $i$ elementos se rotará después de realizar el algoritmo de Heap en los primeros $i$ elementos. Observe que, después de 1 iteración del bucle for, al realizar el algoritmo de Heap en $A$ , $A$ gira 1 hacia la derecha. Según la hipótesis de inducción, se supone que los primeros $i$ elementos rotarán. Después de esta rotación, el primer elemento de $A$ se intercambiará en el búfer que, cuando se combina con la operación de rotación anterior, en esencia realizará una rotación en la matriz. Realice esta operación de rotación $n$ veces y la matriz volverá a su estado original. Esto se ilustra a continuación para el caso . $n=i+1$ $n=5$

1,2,3,4,5 ... Matriz original4,1,2,3,5... 1.ª iteración (Permutar subconjunto/Rotar subconjunto)5,1,2,3,4... 1.ª iteración (intercambio)3,5,1,2,4... 2da iteración (Permutar subconjunto/Rotar subconjunto)4,5,1,2,3... 2da iteración (Intercambio)2,4,5,1,3... 3.ª iteración (Permutar subconjunto/Rotar subconjunto)3,4,5,1,2... 3.ª iteración (intercambio)1,3,4,5,2... 4ta iteración (Permutar subconjunto/Rotar subconjunto)2,3,4,5,1... 4ta iteración (Intercambio)5,2,3,4,1... Quinta iteración (Permutar subconjunto/Rotar subconjunto)1,2,3,4,5... 5ta iteración (Swap)... El estado final de la matriz está en el mismo orden que el original

La prueba de inducción para la afirmación ya está completa, lo que ahora conducirá a por qué el algoritmo de Heap crea todas las permutaciones de la matriz $A.$ Una vez más demostraremos por inducción la exactitud del algoritmo de Heap.

Base: el algoritmo de Heap permuta trivialmente una matriz $A$ de tamaño $1$ ya que la salida $A$ es la única permutación de $A$ .

Inducción: suponga que el algoritmo de Heap permuta una matriz de tamaño $i$ . Usando los resultados de la prueba anterior, cada elemento de $A$ estará en el "búfer" una vez cuando se permuten los primeros $i$ elementos. Debido a que se pueden realizar permutaciones de una matriz alterando alguna matriz $A$ mediante la eliminación de un elemento $x$ de $A$ y luego agregando $x$ a cada permutación de la matriz alterada, se deduce que el algoritmo de Heap permuta una matriz de tamaño , para el "búfer" en esencia, contiene el elemento eliminado y se adhiere a las permutaciones del subconjunto de tamaño $i$ . Debido a que cada iteración del algoritmo de Heap tiene un elemento diferente de $A$ que ocupa el búfer cuando se permuta el subarreglo, cada permutación se genera ya que cada elemento de $A$ tiene la posibilidad de agregarse a las permutaciones de la matriz $A$ sin el elemento del búfer. $i+1$

Malas implementaciones frecuentes

Es tentador simplificar la versión recursiva dada anteriormente reduciendo las instancias de llamadas recursivas. Por ejemplo, como:

procedimiento generar ( k : entero , A : matriz de cualquiera ) : si k = 1, entonces salida ( A ) en caso contrario                // Llama recursivamente una vez por cada k para i := 0 ; yo < k ; i += 1 genera ( k - 1 , A ) // elección de intercambio que depende de la paridad de k (par o impar) si k es par entonces // no opera cuando i == k-1 swap ( A [ i ] , A [ k - 1 ]) else // XXX intercambio adicional incorrecto cuando i==k-1 swap ( A [ 0 ] , A [ k - 1 ]) finaliza si                                fin por fin si

Esta implementación logrará producir todas las permutaciones pero no minimizará el movimiento. A medida que las pilas de llamadas recursivas se desenrollan, se generan intercambios adicionales en cada nivel. La mitad de estos serán no operativos y dónde , pero cuando es extraño, resulta en intercambios adicionales del con el elemento. $A[i]$ $A[k-1]$ $i==k-1$ $k$ $kth$ $0º$

Estos intercambios adicionales alteran significativamente el orden de los elementos del prefijo. $k-1$

Los intercambios adicionales se pueden evitar agregando una llamada recursiva adicional antes del bucle y los tiempos de bucle (como arriba) o los tiempos de bucle y verificando que sean menores que como en: $k-1$ $k$ $i$ $k-1$

procedimiento generar ( k : entero , A : matriz de cualquiera ) : si k = 1, entonces salida ( A ) en caso contrario                // Llama recursivamente una vez por cada k para i := 0 ; yo < k ; i += 1 genera ( k - 1 , A ) // evita el intercambio cuando i==k-1 if ( i < k - 1 ) // la elección del intercambio depende de la paridad de k si k es par entonces intercambia ( A [ i ] , A [ k - 1 ]) else swap ( A [ 0 ] , A [ k - 1 ]) fin si fin si fin por fin si

La elección es principalmente estética, pero esto último implica comprobar el valor dos veces más a menudo. $i$

Ver también

Algoritmo de Steinhaus-Johnson-Trotter

Referencias

^ Montón, BR (1963). "Permutaciones por intercambios". La revista informática . 6 (3): 293–4. doi : 10.1093/comjnl/6.3.293 .
^ Sedgewick, R. (1977). "Métodos de generación de permutaciones". Encuestas de Computación ACM . 9 (2): 137–164. doi : 10.1145/356689.356692 . S2CID 12139332.
^ Sedgewick, Robert (4 de junio de 2020). "una charla sobre Algoritmos de Generación de Permutaciones" (PDF) .