LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

No debe confundirse con el montón .

Un mapa de las 24 permutaciones y los 23 intercambios utilizados en el algoritmo de Heap permutando las cuatro letras A (ámbar), B (azul), C (cian) y D (rojo oscuro)

Diagrama de rueda de todas las permutaciones de longitud. $${\ displaystyle n = 4} generado por el algoritmo de Heap, donde cada permutación está codificada por colores (1 = azul, 2 = verde, 3 = amarillo, 4 = rojo).

El algoritmo del montón genera todas las permutaciones posibles de n objetos. BR Heap lo propuso por primera vez en 1963. ^[1] El algoritmo minimiza el movimiento: genera cada permutación de la anterior mediante el intercambio de un solo par de elementos; los otros elementos n −2 no se alteran. En una revisión de 1977 de los algoritmos de generación de permutación, Robert Sedgewick concluyó que en ese momento era el algoritmo más efectivo para generar permutaciones por computadora. ^[2]

La secuencia de permutaciones de n objetos generados 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 el OEIS ).

Detalles del algoritmo [ editar ]

Para una colección $${\ displaystyle C}que contiene n elementos diferentes, Heap encontró un método sistemático para elegir en cada paso un par de elementos para cambiar a 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 del$${\ displaystyle k}Elementos iniciales de la colección. Inicialmente$${\ displaystyle k == n} y posteriormente {\ displaystyle k . Cada paso genera el$${\ displaystyle k!} permutaciones que terminan con el mismo $${\ displaystyle nk}elementos finales Hace esto llamándose una vez con el$${\ displaystyle kth} elemento inalterado y luego $${\ displaystyle k-1} veces con el ($${\ displaystyle kth}) elemento intercambiado para cada una de las iniciales $${\ displaystyle k-1}elementos. Las llamadas recursivas modifican la inicial$${\ displaystyle k-1}se necesitan elementos y una regla en cada iteración para seleccionar cuál se intercambiará con la última. El método del montón 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 elemento final siempre se intercambia con el primero.

procedimiento  generate ( k  :  integer ,  A  :  array  of  any ) : 
    si  k  =  1  entonces 
        salida ( A ) 
    sino 
        // Genera permutaciones con kth sin alterar 
        // Inicialmente k == longitud (A) 
        generar ( k  -  1 ,  A )

        // Genera permutaciones para kth intercambiadas con cada inicial k-1 
        para  i  : =  0 ;  i  <  k - 1 ;  i  + =  1  do 
            // La opción de intercambio depende de la paridad de k (par o impar) 
            si  k  es  par y  luego 
                intercambia ( A [ i ] ,  A [ k - 1 ])  // indexado a cero, el kth está en k- 1 
            intercambio más 
                ( A [ 0 ] , A [ k - 1 ]) 
            finaliza  si se 
            genera ( k  -  1 ,  A )

        fin  por 
    fin  si

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

El procedimiento  generate ( n  :  integer ,  A  :  array  of  any ) : 
    // c es una codificación del estado de la pila. c [k] codifica el contador for-loop para cuando generate (k + 1, A) se llama 
    c  :  matriz  de  int

    para  i  : =  0 ;  i  <  n ;  i  + =  1  do 
        c [ i ]  : =  0 
    final  para

    salida ( A )
    
    // i actúa de manera similar al puntero de la pila 
    i  : =  0 ; 
    mientras que  i  <  n  do 
        if   c [ i ]  <  i  entonces 
            si  yo  es  incluso  entonces 
                swap ( A [ 0 ] ,  A [ i ]) 
            else 
                swap ( A [ c [ i ]] ,  A [ i ]) 
            finalizan  si la 
            salida ( A )
            // Se ha producido un intercambio que finaliza el ciclo for. Simule el incremento del contador for-loop 
            c [ i ]  + =  1 
            // Simule la llamada recursiva que llega al caso base llevando el puntero al análogo del caso base en la matriz 
            i  : =  0 
        else 
            // Llamada a generar (i + 1 , A) ha finalizado cuando el ciclo for ha terminado. Restablezca el estado y simule estallar la pila incrementando el puntero. 
            c [ i ]  : =  0 
            i  + =  1 
        final  si 
    finaliza  mientras

Prueba [ editar ]

En esta prueba, usaremos la implementación a continuación como Algoritmo de Heap. Si bien no es óptimo (consulte la sección a continuación), la implementación sigue siendo correcta y producirá todas las permutaciones. La razón para usar la siguiente implementación es que el análisis es más fácil y ciertos patrones pueden ilustrarse fácilmente.

procedimiento  generar ( k  :  entero ,  A  :  matriz  de  cualquiera ) : 
    si  k  =  1,  entonces 
          salida ( A ) 
    más 
        para  i  : =  0 ;  i  <  k ;  i  + =  1  no 
            genero ( k  -  1 ,  A ) 
            si  k  es  incluso  entonces 
                intercambiar ( A [ i ],  A [ k - 1 ]) 
            otro 
                intercambio ( A [ 0 ] ,  A [ k - 1 ])  
            finaliza  si

        fin  por 
    fin  si

Reclamación: Si matriz A tiene una longitud n , a continuación, realizar el algoritmo de Heap o bien resultar en un ser "girada" a la derecha en 1 (es decir, cada elemento se desplaza a la derecha con el último elemento que ocupa la primera posición) o resultar en un ser inalterado, dependiendo de si n es par o impar, respectivamente.

Base: la afirmación anterior es trivialmente válida para $${\ displaystyle n = 1}ya que el algoritmo de Heap simplemente devolverá A sin modificaciones en orden.

Inducción: suponga que la afirmación es cierta para algunos $${\ displaystyle i \ geq 1}. Luego tendremos que manejar dos casos para$${\ displaystyle i + 1}: $${\ displaystyle i + 1} es par o impar

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

1,2,3,4 ... Matriz original
1,2,3,4 ... primera iteración (subconjunto Permute)
4,2,3,1 ... 1ra iteración (Intercambie el 1er elemento en "buffer")
4,2,3,1 ... 2a iteración (subconjunto de permuta)
4,1,3,2 ... 2da iteración (Intercambie el 2do elemento en "buffer")
4,1,3,2 ... 3ra iteración (subconjunto de permuta)
4,1,2,3 ... 3ra iteración (Intercambie el 3er elemento en "buffer")
4,1,2,3 ... 4ta iteración (subconjunto Permute)
4,1,2,3 ... 4ta iteración (Intercambie el 4to elemento en "buffer") ... La matriz alterada es una versión rotada del original

Si, para A ,$${\ displaystyle n = i + 1}es extraño, entonces el subconjunto de los primeros elementos i se rotará después de realizar el algoritmo de Heap en los primeros elementos i . Observe que, después de 1 iteración del ciclo for, cuando realiza el algoritmo de Heap en A , A gira a la derecha en 1. Según la hipótesis de inducción, se supone que los primeros elementos i 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, esencialmente 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$${\ displaystyle n = 5}.

1,2,3,4,5 ... Matriz original
4,1,2,3,5 ... primera iteración (Subconjunto de permutar / Subconjunto de rotación)
5,1,2,3,4 ... primera iteración (Swap)
3,5,1,2,4 ... 2da iteración (Subconjunto de permuta / Subconjunto de rotación)
4,5,1,2,3 ... 2a iteración (Swap)
2,4,5,1,3 ... 3ra iteración (Subconjunto de permutar / Subconjunto de rotación)
3,4,5,1,2 ... 3ra iteración (Swap)
1,3,4,5,2 ... 4ta iteración (Subconjunto de permutar / Subconjunto de rotación)
2,3,4,5,1 ... 4ta iteración (Swap)
5,2,3,4,1 ... 5ta iteración (Subconjunto de permutar / Subconjunto de rotación)
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 reclamación se ha completado, que ahora llevará a qué algoritmo de Montón crea todas las permutaciones de la matriz A . Una vez más, probaremos por inducción la corrección del algoritmo de Heap.

Base: Algoritmo de Heap permuta trivialmente una matriz A de tamaño 1 como outputing A es el único y 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, se notará que cada elemento de A estará en el "búfer" una vez cuando los primeros elementos i estén permutados. Debido a que se pueden realizar permutaciones de una matriz alterando alguna matriz A a través de 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$${\ displaystyle i + 1}, porque el "búfer" en esencia 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 que ocupa el búfer cuando se permuta la submatriz, 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 de búfer.

Implementaciones erróneas frecuentes [ editar ]

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

procedimiento  generar ( k  :  entero ,  A  :  matriz  de  cualquiera ) : 
    si  k  =  1  entonces 
          salida ( A ) 
    más

        // Llama recursivamente una vez por cada k 
        para  i  : =  0 ;  i  <  k ;  i  + =  1  sí 
            genera ( k  -  1 ,  A ) 
            // la opción de intercambio depende de la paridad de k (par o impar) 
            si  k  es  par  entonces 
                // no-op cuando i == k-1 
                swap ( A [ i ] ,  A [ k - 1 ]) 
            más 
                // XXX intercambio adicional incorrecto cuando i == k-1 
                intercambio ( A [0 ] ,  A [ k - 1 ])  
            finaliza  si

        fin  por 
    fin  si

Esta implementación tendrá éxito en 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 no-ops de$${\ displaystyle A [i]} y $${\ displaystyle A [k-1]} dónde $${\ displaystyle i == k-1} pero cuando $${\ displaystyle k} es extraño, da como resultado intercambios adicionales de $${\ displaystyle kth} con el $${\ displaystyle 0th} elemento.

$${\ displaystyle n}	$${\ displaystyle n! -1}	permutas	adicional = intercambios $${\ displaystyle - (n! -1)}
1	0 0	0 0	0 0
2	1	1	0 0
3	5 5	6 6	1
4 4	23	27	4 4
5 5	119	140	21
6 6	719	845	126
7 7	5039	5922	883
8	40319	47383	7064
9 9	362879	426456	63577

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

Los intercambios adicionales se pueden evitar agregando una llamada recursiva adicional antes del bucle y bucle $${\ displaystyle k-1}veces (como arriba) o bucle$${\ displaystyle k} veces y comprobando que $${\ displaystyle i} es menos que $${\ displaystyle k-1} como en:

procedimiento  generar (k  :  entero ,  A  :  matriz  de  cualquiera ) : 
    si  k  =  1  entonces 
          salida ( A ) 
    más

        // Llama recursivamente una vez por cada k 
        para  i  : =  0 ;  i  <  k ;  i  + =  1  do 
            generate ( 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  incluso  entonces 
                    intercambio ( A [ i ] ,  A [ k - 1 ]) 
                más 
                    intercambiar( A [ 0 ] ,  A [ k - 1 ]) 
                fin  si 
            fin  si 
        fin  por 
    fin  si

La elección es principalmente estética, pero la última da como resultado la comprobación del valor de $${\ displaystyle i} el doble de seguido.