Algoritmo para construir las permutaciones de una lista

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! Como se observa en la Figura, para tres elementos obtenemos P(3) = 3! = 6.

Para ser coherentes con mucha documentación, matemáticamente es preferible P(n, k) denominadas las k-permutaciones, de tal forma que P(n, n) = P(n) y así se prescinde del término variaciones V(n, k), que pasaría a ser P(n, k). Sin embargo en la aplicación y en esta serie de temas vamos a considerar las permutaciones de forma separada de las variaciones.

El siguiente algoritmo ya lo presenté hace años en el tema permutar un array que se basa en esta fórmula:

// P(n) = n! = n × (n-1)! = n × P(n-1)
function permute1(list){
    let n = list.length;
    let result = [];
    if (n<2) {
        //iter += 1;
        result.push(list);
    } else if (n===2) {
        //iter += 1;
        result = [[list[0], list[1]], [list[1], list[0]]];
    } else {
        //iter += 1
        for (let j=0; j<n; j++) {
            //iter += n+1;
            let listMinor = list.slice(0,j).concat(list.slice(j+1));
            let subResult = permute1(listMinor);
            for (let i=0; i<subResult.length; i++){
                //iter += subResult[i].length+1;
                result.push([list[j], ...subResult[i]]);
            }
        }
    }
    return result;
}

Definimos la recurrencia del algoritmo anterior:

Vimos en aquella página que esta recurrencia no es equiparable al modelo de ecuación característica de coeficientes constantes:

En aquel momento hice un despliegue o desarrollo de la recurrencia desde n hasta el caso trivial. A continuación se expone el mismo desarrollo y solución alcanzada en ese tema. Para simplificar sustituiremos P(n) = n² + n + 1 y lo repondremos al finalizar. En la iteración n tenemos:

Iteración n-1

Iteración n-2

Seguimos iterando hasta llegar a la iteración 3

Llegamos al caso trivial donde T(2) = 1 y como ∑_k=3..n (n-k+3) n!= 1/2 (n²+n-6) n!

Reponiendo P(k) = k²+k+1

Y finalmente lo ponemos como sigue

Como estamos practicando con la técnica de la función generadora o generatriz, en el resto de esto tema nos ocuparemos de obtener esa solución, o alguna equivalente, con esa técnica.

Resolución con función generadora exponencial

La técnica del desarrollo de la recurrencia del primer apartado fue bastante fácil de llevar a cabo. Sin embargo intentarlo mediante una función generadora (o generatriz) no me ha sido tan sencillo, como veremos a continuación. Tuve que estudiar algunas cosas que expongo en un tema anterior recurrencias con coeficientes variables, pues en un momento dado tendremos que utilizarlo.

Empecemos con la siguiente definición:

Incrementamos índices para evitar negativos:

Vemos que (n+1) es un factor comun de la derecha, por lo que hacemos esto

de donde obtenemos esta recurrencia:

Tal como comentamos en el tema anterior sobre desplazamiento del caso base, el caso base de esta recurrencia se encuentra también desplazado y, a efectos de la recurrencia, es T(2) = 1, puesto que el algoritmo nunca podrá bajar de n=2 cuando partimos de un valor superior. Entonces usaremos la función generadora exponencial siguiente:

La única condición inicial que aplicaremos es la del caso base efectivo T(2), por lo que sólo consideraremos G₂(x), ignorándose G₀(x) y G₁(x):

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

Veamos que es cada término anterior como una función f(x, y). Empecemos por lo más evidente en [3]:

Veamos el término de la izquierda en [3]:

Veamos el término de la derecha en [3], que también puede comprobarse Wolframalpha:

Y por último el término central en [3] es como sigue (ver desarrollo en el desplegable siguiente):

Sustituimos [4], [5], [6], [7] en [3]:

Despejando G(x) queda:

Intentemos simplificar:

Busquemos una serie para cada término de [9], empezando por los términos que no tienen el exponencial e^x. Uno de ellos es el siguiente, cuyo desarrollo de Taylor puede ver en el desplegable siguiente. Observe que ajustamos el índice del sumatorio a n≥2 para hacerlo coincidir con la serie que deseamos obtener.

El siguiente en [9] tiene este serie, con el desarrollo de Taylor en el desplegable, viendo que volvemos a ajustar el índice del sumatorio a n≥2 para hacerlo coincidir con la serie que deseamos obtener.

Los términos de la derecha en [9] que no tienen e^x van quedando así:

El término restante 6x+9-10/(1-x) se resuelve en el siguiente desplegable.

Y ahora vamos por los tres términos de la izquierda en [9] que tienen e^x. Para resolver esto vease primero lo que explicamos en un tema anterior sobre las K-Tuplas, siendo k ∈ ℤ, k≥0

Identificamos en lo que sigue en cada sumando x⁰, x¹, x² siendo k = 0, 1, 2:

Veamos el término general

Por lo tanto

Se ajusta n≥2 apareciendo el componente 1+4x. Los términos generales [10] y [11] componen la solución, observando que el término 1+4x se anula con -1-4x, algo que no es casual, pues proviene del ajuste de índices al caso base, tal como veremos en un tema posterior sobre casos bases genéricos en una recurrencia:

Tenemos entonces el siguiente término general para n≥2:

Esta solución produce la secuencia 1, 34, 253, 1896, 15739, 145510, ... para n≥2 tal como vemos en Wolframalpha (incluso también expandiendo la propia recurrencia en Wolframalpha). Podríamos dejarlo así, pero sin embargo vamos a ajustar el índice del sumatorio interior para luego facilitar la comparación con la solución que alcanzamos con el despliegue:

En lo anterior vemos que -10 se anula con +10, algo que no es casual, pues proviene del ajuste de índices al caso base, tal como veremos en un tema posterior sobre casos bases genéricos en una recurrencia. Entonces este será nuestro término general final, que produce la misma secuencia 1, 34, 253, 1896, 15739, 145510, ... para n≥2 como se puede comprobar en Wolframalpha

Esta solución es aparentemente distinta a la que obtuvimos con el desglose de la recurrencia y que repetimos en el primer apartado, pero son equivalentes como vemos en Wolframalpha produciendo esa misma secuencia. En unos apartados más abajo demostraremos que esto es cierto.

Soluciones equivalentes del algoritmo para construir permutaciones

Para ver la equivalencia entre [13] y [14] primero restamos los términos entre paréntesis, el segundo del primero, prescidiendo de n! y (n²+n)/2 que aparece en ambas, vemos que resulta cero, siendo por tanto ambas soluciones iguales, lo que se puede comprobar en Wolframalpha

Intentándolo de otra forma también con ayuda de Wolframalpha resolviendo el sumatorio en [14] obtenemos:

En el siguiente apartado demostraremos el resultado anterior. Por ahora sígamos con nuestro propósito viendo que en el resumen que vimos en el tema anterior las soluciones equivalentes de las K-Tuplas K(n) = e Γ(n+1, 1) = ∑_j=0..n n! / j! por lo que sustituimos en lo anterior

Ajustaremos el índice:

Quedando

Sustituyendo esto en [14]

Vemos que llegamos al resultado equivalente obtenido en [13].

Equiparar soluciones usando K-Tuplas y Convoluciones exponenciales de factoriales y potencias

En [16] nos apoyamos en Wolfram Alpha por medio de la función gamma incompleta para alcanzar el resultado

Multiplicaremos ambos lados por n! para facilitar la demostración:

Para demostrarlo hemos de recurrir a los temas de las K-Tuplas y de las convoluciones exponenciales de factoriales y potencias que hemos visto en temas anteriores. Por un lado tenemos las K-Tuplas K(n, k):

Y por otro las siguientes equivalencias de las convoluciones exponenciales EC(n, k), con k=0:

Con k=1

Y con k=2

Partimos de la parte izquierda en [17] donde insertamos esas equivalencias tras hacer los correspondientes ajustes en los índices de los sumatorios:

En el paso [21] separamos en tres series ajustando el índice a cero. En el paso [22] aplicamos [20], [19] y [18] respectivamente. Finalmente hemos alcanzado el resultado [17] lo que equipara las dos soluciones equivalente del algoritmo que hemos visto:

Ajuste de las soluciones para valores inferiores al caso base

Las dos soluciones equivalentes son de una recurrencia cuyo caso base está en n=2:

Esto quiere decir que los valores inferiores n≤2 no estan definidos por esa solución, pues en lugar de obtenerse T(0) = 1, T(1) = 1 vemos que se obtienen valores negativos y diferentes en ambos casos:

Por lo tanto para que el coste real que produce el algoritmo sea coherente con la solución hemos de imponer el máximo entre uno y el valor obtenido:

Coste asintótico del algoritmo básico para permutar

Cuando analicé este algoritmo hace años en coste asintótico del algoritmo para permutar encontré que era del orden T(n) ∈ O((n+2)!). Como el algoritmo siempre produce resultados parciales copiados, este coste es el mismo para ambos casos.