El algoritmo de Heap para generar permutaciones

Las permutaciones de una lista con n elementos distintos son todas las sublistas ordenadas con n elementos distintos que se pueden generar. Se denota generamente como P(n). Su valor es P(n) = n!

El algoritmo de Heap genera las permutaciones de forma más eficiente que el que hemos usado en el tema anterior. Se basa en generar cada permutación desde una previa intercambiando una pareja de elementos cada vez. En la Figura puede ver como se van intercambiando posiciones desde la lista inicial [0, 1, 2] generando las permutaciones {[0, 1, 2], [1, 0, 2], [2, 0, 1], [0, 2, 1], [1, 2, 0], [2, 1, 0]}. Implementamos este algoritmo con permute2(list):

function permute2(list=[], n=list.length, result=[]){
    if (n<=1) {
        iter += 1;
        if (withCopyCost) iter += list.length;
        result.push(copy(list));
    } else {
        iter += 1;
        for (let j=0; j<n; j++){
            iter += 1;
            permute2(list, n-1, result);
            if (j<n-1) {
                if (n%2===0){
                    [list[j], list[n-1]] = [list[n-1], list[j]];
                } else {
                    [list[0], list[n-1]] = [list[n-1], list[0]];
                }
            }
        }
    }
    return result;
}

Se puede encontrar otro algoritmo equialente que apenas se diferencia con el anterior y que tiene el mismo coste. La diferencia está en el bucle y en la parte de intercambio, no necesitando la comprobación de paridad n%2===0 aunque se producen intercambios infructuosos con los mismos índices. En cualquier caso el número de iteraciones es exactamente el mismo en ambos casos. Este es el algoritmo del que vamos a analizar su coste en este tema y así evitamos manejar la paridad de la iteración en el coste:

function permute3(list=[], n=list.length, result=[]){
    if (n<=1) {
        iter += 1;
        if (withCopyCost) iter += list.length;
        result.push(copy(list));
    } else {
        iter += 1;
        for (let j=n-1; j>-1; j--){
            iter += 1;
            [list[j], list[n-1]] = [list[n-1], list[j]];
            permute3(list, n-1, result);
            [list[j], list[n-1]] = [list[n-1], list[j]];
        }
    }
    return result;
}

Analizaremos permute3(list). La definición de la recurrencia de coste queda así:

Este algoritmo ya lo expuse en el tema Permutar con el algoritmo de Heap hace años. Como es una recurrencia de coeficientes variables, hice un despliegue o desarrollo de la recurrencia para obtener la solución. Replico aquí lo mismo que expuse en ese tema. En la iteración n al inicio tenemos:

Iteración n-1:

Iteración n-2:

Iteración n-3:

Seguimos hasta alcanzar la iteración 2

Lo resaltado en azul tiene los términos del rango [2..n-1]. El caso trivial es T(1) = 1, con lo que los dos resaltes en amarillo son iguales:

Vemos que lo resaltado en amarillo sigue la secuencia de la serie con rango [2..n-1] resaltada en azul, por lo que podemos agruparlos en una serie que se incrementa en un término con el rango ahora [2..n]:

Deducimos el término general como n!/(n-j+1)! con j ∈ [2..n] quedando:

Observe en Wolframalpha que se obtiene la secuencia 1, 5, 19, 81, 411, 2473, 17319, ... para n≥1. Para n=0 esta recurrencia no ofrece valor alguno, siendo establecido por la definición como T(0) = 1. Se obtiene la misma secuencia si resolvemos directamente la recurrencia en Wolframalpha.

Algoritmo de Heap con función generadora

Vamos a obtener esa solución usando una función generadora o generatriz. Partimos de:

Incrementamos índices para evitar negativos:

Dividimos entre n+1:

Usamos la función generadora exponencial con el caso base desplazado en n=1 (ver lo que comentamos en el tema desplazamiento del caso base):

Las condiciones iniciales son las siguientes, de las que sólo necesitaremos G₁(x):

Aplicamos xⁿ / n! a la recurrencia [1] y sumamos:

El término de la izquierda en [3] es:

El término después del signo igual en [3] es obvio:

Y ahora el término de la derecha en [3]:

Obviamente el término ∑_n≥0 xⁿ/n! = e^x. Sustituyendo [4], [5] y [6] en [3]:

De donde:

El penúltimo sumando de la derecha en [7] es una geométrica:

Los otros dos términos en [7] se identifican con las K-Tuplas para valores de k=0 y k=1:

donde K(n, k) es, entre otras formas, así:

Entonces con k=0 y k=1 nos queda:

Agrupando [8] y [9] en [7] tenemos la serie de G(x), donde se observa que los tres términos por fuera de los sumatorios se anulan:

El término general es:

Observe en Wolframalpha que se obtiene la secuencia 1, 5, 19, 81, 411, 2473, 17319, ... para n≥1, la misma que obtuvimos en el apartado anterior.

Hacemos un ajuste manual con el sumatorio para reflejar el índice j≥2 del algoritmo y poder compararlo con la solución alcanzada en el apartado anterior:

obteniéndose finalmente

Se comprueba que tiene la misma secuencia en Wolframalpha, por lo que esta solución es equivalente a la que alcanzamos en el apartado anterior con el desarrollo de la recurrencia:

Demostrar la equivalencia de ambas soluciones usando las K-Tuplas

En el tema de las K-Tuplas demostramos esta igualdad:

Si tomamos n+1 y k=0 tenemos la siguiente igualdad:

ajustando los índices

simplificando:

despejando el primer sumatorio:

Ajustamos índices j≥2 en ambos lados:

Entonces tras simplificar todo lo que podamos:

Si sustituimos este sumatorio en [10] tendremos que llegar a [11]:

Siendo esta solución la esperada para demostrar que [10] es lo mismo que [11].

Coste de copia del Algoritmo de Heap

El análisis del coste visto en apartados anteriores no contempla el coste de copiar los resultados parciales. Dado que cuando tenemos un resultado parcial al llegar al caso base hemos de traspasarlo al array de resultados, si no hacemos una copia estaremos almacenando la misma referencia y, por tanto, el resultado al final contendría n! resultados iguales que la última permutación generada. Para evitarlo hacemos una copia del array de cada resultado parcial:

...
if (n<=1) {
    iter += 1;
    if (withCopyCost) iter += list.length;
    result.push(copy(list));
} else {
...

Como hay n! permutaciones para un conjunto de n elementos, entonces el coste de copiarlos será n n!, quedando el término general con coste de copia de esta forma para ambas soluciones equivalentes:

Coste asintótico del Algoritmo de Heap

Cuando analicé este algoritmo hace años en coste asintótico del algoritmo de Heap encontré que el coste sin copia era del orden del factorial T(n) ∈ O(n!). Pero con coste de copia habría que sumar n n! por lo que se elevaba a T(n) ∈ O((n+1)!).

El algoritmo básico que presentamos en el tema anterior tenía un coste asintótico de T(n) ∈ O((n+2)!), con o sin copia, pues ese algoritmo siempre produce resultado parciales copiados. En cualquier caso el algoritmo de Heap reduce desde (n+2)! hasta n! en el caso de coste sin copia y hasta (n+1)! con copia. No parece mucho reducir una unidad de orden en el factorial, pero tal como comentamos en ese tema, si por ejemplo bajamos de 9! = 362880 a 8! = 40320 supone evitarnos 322560 iteraciones: cerca del 89% menos. Con ningún otro tipo de coste, ni siquiera el exponencial, supone tanto ahorro bajar una unidad de orden de coste. Esto se observa en la Figura.

Además en el enlace a algoritmo de Heap que pusimos al principio dice que en 1977 Robert Sedgewick concluyó que el algoritmo de Heap era el más eficiente para generar permutaciones en aquel momento. Y aunque no expone lo contrario, suponemos que esto sigue siendo cierto al menos con computación convencional.