El algoritmo de Heap

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 único par de elementos; los otros n −2 elementos no se ven afectados. En una revisión de 1977 sobre 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. Por lo tanto, existe una secuencia infinita de permutaciones generada por el algoritmo de Heap (secuencia A280318 en el OEIS ) .

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

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

// Imprime las k! permutaciones de A en las que los primeros k elementos se permutan de todas las maneras. // Para obtener todas las permutaciones de A, usa k := longitud de A. // // Si k > longitud de A, intentará acceder a A fuera de los límites. // Si k <= 0 no habrá salida (un array vacío no tiene permutaciones) procedimiento permutaciones ( k : entero , A : array de cualquier ) : si k = 1 entonces imprimir ( A ) sino // permutaciones con el último elemento fijo permutaciones ( k - 1 , A ) // permutaciones con el último elemento intercambiado para i := 0 ; i < k - 1 ; i += 1 hacer si k es par entonces intercambiar ( A [ i ] , A [ k - 1 ]) sino intercambiar ( A [ 0 ] , A [ k - 1 ]) fin si permutaciones ( k - 1 , A ) fin para fin si

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

procedimiento permutaciones ( n : entero , A : matriz de cualquier ) : // c es una codificación del estado de la pila. // c[k] codifica el contador del bucle for para cuando se llama a permutaciones(k + 1, A) c : matriz de enterospara i := 0 ; i < n ; i += 1 hacer c [ i ] := 0 fin parasalida ( A ) // i actúa de forma similar a un puntero de pila i := 1 ; mientras i < n hacer si c [ i ] < i entonces si i es par entonces intercambiar ( A [ 0 ] , A [ i ]) sino intercambiar ( A [ c [ i ]] , A [ i ]) fin si salida ( A ) // Se ha producido un intercambio, finalizando el bucle while. Simular el incremento del contador del bucle while c [ i ] += 1 // Simular una llamada recursiva que alcanza el caso base llevando el puntero al análogo del caso base en el array i := 1 sino // La llamada a permutations(i+1, A) ha terminado ya que el bucle while ha finalizado. Reiniciar el estado y simular la extracción de la pila incrementando el puntero. c [ i ] := 0 i += 1 fin si fin mientras

En esta demostración, utilizaremos la siguiente implementación como algoritmo de Heap, ya que facilita el análisis y permite ilustrar fácilmente ciertos patrones. Si bien no es óptima (no minimiza los movimientos, como se describe en la sección siguiente), la implementación es correcta y generará todas las permutaciones.

// Imprime las k! permutaciones de A en las que los primeros k elementos se permutan de todas las maneras. // Para obtener todas las permutaciones de A, usa k := longitud de A. // // Si k > longitud de A, intentará acceder a A fuera de los límites. // Si k <= 0 no habrá salida (un array vacío no tiene permutaciones). procedimiento permutaciones ( k : entero , A : array de cualquier ) : si k = 1 entonces imprimir ( A ) sino para i := 0 ; i < k ; i += 1 hacer permutaciones ( k - 1 , A ) si k es par entonces intercambiar ( A [ i ] , A [ k - 1 ]) sino intercambiar ( A [ 0 ] , A [ k - 1 ]) fin sifin para fin si

Afirmación: Si el array A tiene longitud n , entonces permutations(n, A)el resultado será que A permanezca sin cambios, si n es impar, o, si n es par, entonces A se rotará a la derecha en 1 (el último elemento se desplaza delante de los demás elementos).

Base: Si el array A tiene longitud 1, entonces permutations(1, A)se mostrará A y el proceso se detendrá, por lo que A permanece sin cambios. Dado que 1 es impar, esto es lo que se afirmó, por lo que la afirmación es cierta para arrays de longitud 1.

Inducción: Si la afirmación es cierta para arreglos de longitud l ≥ 1, entonces demostramos que también lo es para arreglos de longitud l + 1 (junto con el caso base, esto prueba que la afirmación es cierta para arreglos de cualquier longitud). Dado que la afirmación depende de si l es par o impar, demostramos cada caso por separado.

Si l es impar, entonces, por la hipótesis de inducción, para un arreglo A de longitud l , permutations(l, A)no cambiará A, y para que la afirmación sea válida para arreglos de longitud l + 1 (que es par), necesitamos demostrar que permutations(l+1, A)rota A a la derecha en 1 posición. Hacer permutations(l+1, A)primero hará permutations(l, A)(dejando A sin cambios ya que l es impar) y luego en cada iteración i del bucle for, intercambiará los elementos en las posiciones i y l (la última posición) en A. El primer intercambio coloca el elemento l (el último elemento) en la posición 0, y el elemento 0 en la posición l . El siguiente intercambio coloca el elemento en la posición l (donde la iteración anterior colocó el elemento original 0) en la posición 1 y el elemento 1 en la posición l . En la iteración final, el intercambio coloca el elemento l - 1 en la posición l , y el elemento en la posición l (donde la iteración anterior colocó el elemento original l - 2) en la posición l - 1. Para ilustrar lo anterior, vea a continuación el caso n = 4.

1,2,3,4 ... matriz original 1,2,3,4 ... 1.ª iteración (submatriz de permutación) 4,2,3,1 ... 1.ª iteración (intercambiar el primer elemento con la última posición) 4,2,3,1 ... 2ª iteración (submatriz de permutación) 4,1,3,2 ... 2ª iteración (intercambiar el segundo elemento con la última posición) 4,1,3,2 ... 3.ª iteración (submatriz de permutación) 4,1,2,3 ... 3.ª iteración (intercambiar el tercer elemento con la última posición) 4,1,2,3 ... 4.ª iteración (submatriz de permutación) 4,1,2,3 ... 4.ª iteración (intercambiar el cuarto elemento con la última posición) La matriz modificada es una versión rotada de la original. 

Si l es par, entonces, por la hipótesis de inducción, para un arreglo A de longitud l , permutations(l, A)rota A a la derecha en 1 posición, y para que la afirmación sea válida para arreglos de longitud l + 1 (que es impar), necesitamos demostrar que permutations(l+1, A)deja A sin cambios. Hacer permutations(l+1, A)en cada iteración i del bucle for, primero hará permutations(l, A)(rotando los primeros l elementos de A en 1 posición ya que l es par) y luego, intercambiará los elementos en las posiciones 0 y l (la última posición) en A. Rotar los primeros l elementos y luego intercambiar el primer y el último elemento es equivalente a rotar todo el arreglo. Dado que hay tantas iteraciones del bucle como elementos en el arreglo, todo el arreglo se rota hasta que cada elemento regresa a donde comenzó. Para ilustrar lo anterior, vea a continuación el caso n = 5.

1,2,3,4,5 ... matriz original 4,1,2,3,5 ... 1.ª iteración (submatriz de permutación, que la rota) 5,1,2,3,4 ... 1.ª iteración (intercambio) 3,5,1,2,4 ... 2ª iteración (submatriz de permutación, que la rota) 4,5,1,2,3 ... 2ª iteración (intercambio) 2,4,5,1,3 ... 3.ª iteración (submatriz de permutación, que la rota) 3,4,5,1,2 ... tercera iteración (intercambio) 1,3,4,5,2 ... 4.ª iteración (submatriz de permutación, que la rota) 2,3,4,5,1 ... 4.ª iteración (intercambio) 5,2,3,4,1 ... 5ª iteración (submatriz de permutación, que la rota) 1,2,3,4,5 ... 5ª iteración (intercambio) El estado final del array está en el mismo orden que el original. 

La demostración por inducción de la afirmación ya está completa, lo que nos permitirá explicar por qué el algoritmo de Heap genera todas las permutaciones del arreglo A. Una vez más, demostraremos por inducción la corrección del algoritmo de Heap.

Base: El algoritmo de Heap permuta trivialmente un arreglo A de tamaño 1 ya que la salida A es la única permutación de A.

Inducción: Supongamos que el algoritmo de Heap permuta un arreglo de tamaño i . Usando los resultados de la demostración anterior, cada elemento de A estará en el "búfer" una vez cuando se permuten los primeros i elementos. Debido a que las permutaciones de un arreglo se pueden hacer alterando algún arreglo A mediante la eliminación de un elemento x de A y luego agregando x a cada permutación del arreglo alterado, se deduce que el algoritmo de Heap permuta un arreglo de tamaño${\displaystyle i+1}$, porque el "buffer" esencialmente contiene el elemento eliminado, que se agrega 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 ocupando el buffer cuando se permuta el subconjunto, cada permutación se genera como cada elemento de A tiene la posibilidad de agregarse a las permutaciones del arreglo A sin el elemento del buffer.

Resulta tentador simplificar la versión recursiva anterior reduciendo el número de llamadas recursivas. Por ejemplo, como:

procedimiento permutaciones ( k : entero , A : arreglo de cualquier ) : si k = 1 entonces imprimir ( A ) de lo contrario// Llama recursivamente una vez para cada k para i := 0 ; i < k ; i += 1 hacer permutaciones ( k - 1 , A ) // elección de intercambio dependiendo de la paridad de k (par o impar) si k es par entonces // no hacer nada cuando i == k-1 intercambiar ( A [ i ] , A [ k - 1 ]) sino // XXX intercambio adicional incorrecto cuando i==k-1 intercambiar ( A [ 0 ] , A [ k - 1 ]) fin sifin para fin si

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

Estos intercambios adicionales alteran significativamente el orden de los${\displaystyle k-1}$elementos de prefijo.

Los intercambios adicionales se pueden evitar agregando una llamada recursiva adicional antes del bucle y repitiendo el bucle.${\displaystyle k-1}$veces (como se indicó anteriormente) o en bucle${\displaystyle k}$tiempos y comprobando que${\displaystyle i}$es menor que${\displaystyle k-1}$como en:

procedimiento permutaciones ( k : entero , A : arreglo de cualquier ) : si k = 1 entonces imprimir ( A ) de lo contrario// Llama recursivamente una vez para cada k para i := 0 ; i < k ; i += 1 hacer permutaciones ( k - 1 , A ) // evitar intercambio cuando i==k-1 si ( i < k - 1 ) // elección de intercambio dependiente de la paridad de k si k es par entonces intercambiar ( A [ i ] , A [ k - 1 ]) sino intercambiar ( A [ 0 ] , A [ k - 1 ]) fin si fin si fin para fin si

La elección es principalmente estética, pero esto último conlleva comprobar el valor de${\displaystyle i}$El doble de veces.

• Algoritmo de Steinhaus-Johnson-Trotter