Permutaciones cíclicas

Una permutación cíclica es una permutación que fija cero o más elementos y mueve el resto de forma cíclica. Cuando no se fija ningún elemento se denomina permutación circular.

En la Figura vemos las permutaciones cíclicas de 4 elementos {a, b, c, d}, que de forma compacta representamos como abcd, tomando 3 ciclos en cada permutación. Un ciclo se presenta con una permutación entre paréntesis, algo como (abc). No separamos los elementos si el conjunto de partida son elementos de una solo caracter (letras o números), en otro caso si los separamos (a b c). Esto nos da posibilidad para usar conjuntos numéricos como {1, 2, 3, ..., n} con n>9. Puede ver más sobre notación de permutaciones cíclicas en el siguiente tema.

Los ciclos son como las particiones que vimos en temas anteriores, en el sentido de que son subconjuntos disjuntos del conjunto de partida. Al ser subconjuntos, el orden de los ciclos en la permutación no importa, con lo que algo como (a)(b)(cd) es lo mismo que (b)(cd)(a) y cualquiera de las otras posibles permutaciones de los ciclos.

Esa primera permutación cíclica (a)(b)(cd) contiene dos ciclos unitarios (a) y (b), siendo los ciclos unitarios como puntos fijos de cada permutación. Y luego tenemos un ciclo con 2 elementos (cd). Este ciclo significa que representa dos permutaciones cd y dc, puesto que al ser cíclicas se refieren a la misma.

Vemos gráficamente el ciclo unitario (bcd) poniendo las letras sobre un círculo:

En ese círculo no hay principio ni final, aunque si podemos hablar de un sentido de giro que es el de las agujas del reloj, por eso hablamos de cíclicas, con lo que bcd = cdb = dbc. Así que en la permutaciones cíclicas de abcd en 2 ciclos siguientes:

encontramos que la primera permutación cíclica (a)(bcd) puede escribirse de tres formas:

y la segunda también de tres formas:

Se observa que todos los ciclos de 3 elementos bcd conforman las 3! = 6 permutaciones de ellos:

Por eso hay menos permutaciones con k ciclos que permutaciones normales, pues para el conjunto abcd hay 4! = 24 permutaciones y hay S(4, 2) = 11 permutaciones con 2 ciclos, donde S(n, k) son los números de Stirling de primera clase que explicaremos en un siguiente apartado.

Estas son todas las 4! = 24 permutaciones cíclicas de 4 elementos:

Se observa que permuteCycles(abcd, 1) tiene (n-1)! = 3! = 6 permutaciones cíclicas, observándose que son las permutaciones de bcd intercalando el elemento a en posiciones sucesivas. Y vemos también que permuteCycles(abcd, 4) tiene n=4 permutaciones cíclicas unitarias. Estas dos casos con k=1 y n=k nos ayudarán a implementar un par de algoritmos para generar las permutaciones cíclicas que veremos después.

Para ver mejor la relación entre las permutaciones normales y su representación cíclica, observe esta tabla para el conjunto M = {1, 2, 3} que genera 3! = 6 permutaciones permute(123) = {123, 132, 213, 231, 312, 321}

Permutaciones cíclicas y números de Stirling de primera clase

Ya vimos en el tema de Subfactoriales y logaritmos los números de Stirling de primera clase, donde denotábamos con S(n, k) los que no tenían signo, definiéndolo como el número de permutaciones de n elementos en k ciclos disjuntos. Por lo tanto S(n, k) cuenta el número de permutaciones cíclicas que estamos viendo en este tema.

Los números de Stirling de primera clase sin signo se calculan con la siguiente recurrencia:

Los primeros valores pueden obtenerse en la aplicación Combine Tools, en la pestaña "Numéricos":

Se observa que la segunda columna k=1 son los valores de las permutaciones (n-1)! siendo las permutaciones circulares donde no se fija ningún elemento, por ejemplo, con cuatro elementos tenemos (4-1)! = 3! = 6 permutaciones circulares, donde cada permutación se conforma en un único ciclo:

Con lo anterior S(n, 1) = (n-1)!, con lo que podemos establecer esta recurrencia alternativa que nos servirá para implementar un segundo algoritmo para generar las permutaciones cíclicas:

Otra recurrencia que involucra el binomial es la siguiente:

A continuación exponemos otras cosas relacionadas con los números de Stirling de primera clase. En primer lugar algunas identidades básicas, con comentarios y/o demostración en el desplegable adjunto a cada entrada:

Por otro lado no debemos confundir S(n, k) sin signo con los que tienen signo s(n, k) que obedece a la recurrencia similar:

con estos valores numéricos

Ambas se equiparan así:

Los números de Stirling de primera clase son los coeficientes s(n, k) (con signo) del factorial descendente (o falling factorial):

Por ejemplo:

siendo los coeficientes s(3, 3) = 1, s(3, 2) = -3, s(3, 1) = 2 tal como se observa en la tabla de valores anterior.

Por otro lado, los números de Stirling sin signo S(n, k) se corresponden con los coeficientes del factorial ascendente (o símbolo de Pochhammer):

Función generadora de los números de Stirling de primera clase

La función generadora de los números de Stirling de primera clase sin signo es:

y con signo:

Primer algoritmo para generar permutaciones cíclicas

Implementamos un primer algoritmo con la recurrencia que vimos en [1]:

//S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1)
function permuteCycles1(list=[], k=0) {
    let result = [];
    let n = list.length;
    if (n===k) {
        //iter += n;
        result.push(list.map(v => [v]));
    } else if (n===0 || k===0 || n<k) {
        //iter += 1;
        result = [];
    } else {
        //iter += 1;
        let pivot = list[0];
        //iter += n-1;
        let sublist = list.slice(1);
        let res = permuteCycles1(sublist, k-1);
        /* res.length = S(n-1, k-1) */
        for (let p of res) {
            /* p.length = k-1 */
            //iter += 1 + p.length;
            result.push([[pivot], ...p]);
        }
        res = permuteCycles1(sublist, k);
        /* res.length = S(n-1, k) */
        for (let p of res) {
            /* p.length = k ciclos */
            //iter += 1;
            for (let i=0; i<p.length; i++) {
                //iter += 1;
                let cycle = p[i];
                /* cycle.length promedio c =  (n-1)/k */
                for (let j=0; j<cycle.length; j++) {
                    //iter += 1;
                    /* coste copia = k+(n-1) */
                    //iter += p.length + p.reduce((q,v) =>
                    //       (q+=v.length, q), 0);
                    let arr = copy2(p);
                    /* cycle.length = d */
                    //iter += cycle.length;
                    /* es lo mismo que [...cycle.slice(0, j), 
                       pivot, ...cycle.slice(j)] */
                    arr[i] = cycle.toSpliced(j, 0, pivot);
                    result.push(arr);
                }
            }
        }
    }
    return result;
}

Ejecutando el algoritmo en la herramienta Combine Tools para el conjunto abcd con k=2, obtenemos las siguientes S(4, 2) = 11 permutaciones cíclicas:

El siguiente esquema presenta la evolución del algoritmo. Los círculos con un número en su interior representan llamadas al algoritmo que representamos con "S". La llamada inicial con un 0, la primera llamada a permuteCycles1(sublist, k-1) y la segunda llamada a permuteCycles1(sublist, k). Con un fondo negro representan los retornos de esas llamadas, tras lo cual se recomponen los resultados. Los textos en verde son las devoluciones de los casos bases:

0⇒ S(abcd, 2) ⇒
pivot=a sublist=bcd ⇒
1⇒ S(bcd, 1) ⇒
    pivot=b sublist=cd ⇒
    1⇒ S(cd, 0) = ∅ 1⇒ ∅ 1⇒ ∅
    2⇒ S(cd, 1) ⇒
        pivot=c sublist=d ⇒
        1⇒ S(d, 0) = ∅ 1⇒ ∅ 2⇒ ∅ 1⇒ ∅
        2⇒ S(d, 1) = (d) 2⇒ (cd) 2⇒ (bcd), (cbd) 1⇒ (a)(bcd),
                                                            (a)(cbd)
2⇒ S(bcd, 2)
    pivot=b sublist=cd ⇒
    1⇒ S(cd, 1) ⇒
        pivot=c sublist=d ⇒
        1⇒ S(d, 0) = ∅ 1⇒ ∅ 1⇒ ∅ 2⇒ ∅
        2⇒ S(d, 1) = (d) 2⇒ (cd) 1⇒ (b)(cd) 2⇒ (ab)(cd),
                                                       (b)(acd),
                                                       (b)(cad)
    2⇒ S(cd, 2) ⇒
        pivot=c sublist=d ⇒
        1⇒ S(d, 1) = (d) 1⇒ (c)(d) 2⇒ (bc)(d), (c)(bd) 2⇒ 
                                                         (abc)(d),
                                                         (bac)(d),
                                                         (bc)(ad),
                                                         (ac)(bd),
                                                         (c)(abd),
                                                         (c)(bad)
        2⇒ S(d, 2) = ∅ 2⇒ ∅ 2⇒ ∅ 2⇒ ∅
0⇒ (a)(bcd), (a)(cbd), (ab)(cd), (b)(acd), (b)(cad), (abc)(d),
     (bac)(d), (bc)(ad), (ac)(bd), (c)(abd), (c)(bad)

En los casos bases con k=0 o n<k, como la última llamada S(d, 2), se devuelve un array vacío, por lo que los retornos de esas llamadas no aportan resultados. Esto lo vamos a evitar con el segundo algoritmo que veremos después.

Observe que los retornos de la segunda llamada permuteCycles1(sublist, k) agrega el pivote antes de cada elemento en los ciclos. Mientras que los de permuteCycles1(sublist, k-1) de la primera llamada inserta un ciclo al inicio con el pivote, como en esta cadena en la devolución de S(d, 1):

Pasamos ahora a plantear la recurrencia del coste observando el algoritmo y los comentarios, llegando a lo siguiente:

Vemos los dos casos bases n=k y k=0 ∨ n<k. En el caso general observamos tres partes:

• 1 + (n-1) en la entrada al else con la acción list.slice(1) para recortar la lista un elemento.

• T(n-1, k-1) + S(n-1, k) (1 + (k-1)) para la primera llamada recursiva permuteCycles1(sublist, k-1) y el bucle de recomposición de resultados que viene a continuación, bucle con longitud S(n-1, k-1) pues ya vimos en el apartado anterior que son los números de Stirling de primera clase los que cuentan las permutaciones cíclicas para una sublista de longitud n-1 en k-1 ciclos disjuntos. Y es esa cantidad k-1 lo que nos cuesta componer los arrays [[pivot], ...p] para incorporar como permutación cíclica en el resultado.

• T(n-1, k) + S(n-1, k) (1 + k (1 + c (1 + k + (n-1) + d))) para la segunda llamada recursiva permuteCycles1(sublist, k), con S(n-1, k) subresultados que recomponemos en 2 bucles anidados. Uno externo con longitud k ciclos. Y otro interno con la longitud promedio de elementos en cada ciclo que es c = (n-1)/k, pues cada permutación tiene k ciclos con n-1 elementos en total en todos los ciclos de cada permutación.

  Antes de agregar el subresultado al resultado final hay que hacer una copia del mismo, pues como hemos visto otras veces, en otro caso estaríamos pasando la misma referencia. El coste de copia es k+(n-1), pudiendo usar la función copyArray(p) que cuenta las iteraciones o bien usar copy2(p), tal como vimos en un tema anterior sobre particiones.

  Finalmente hay que insertar el pivote entre los elementos de cada ciclo con cycle.toSpliced(j, 0, pivot), pero aquí no podemos usar la longitud promedio de cada ciclo c = (n-1)/k sino la longitud exacta 1 ≤ d ≤ (n-1-k), valor que no he podido determinar con exactitud. Por ejemplo, una permutación cíclica con n-1 = 5 elementos en k = 3 ciclos tiene una longitud promedio del ciclo de c = (n-1)/k = 5/3 ≈ 1.6667. En un caso tenemos (a)(b)(cde) con un ciclo con 3 elementos y 2 ciclos con un elemento siendo el caso extremo con un ciclo con máximo de elementos, observando que la longitud exacta es 1 ≤ d ≤ 3, donde podemos deducir que n-1-(k-1) = 5-(3-1) = 3, así que de forma general sería 1 ≤ d ≤ n-k. Este valor máximo nos servirán después para acotar el coste dado que no pude determinar el valor exacto para d en cada momento.

Simplificando la parte recurrente de la expresión anterior llegamos a

Si hacemos d = 0 eliminando la sentencia iter += cycle.length que cuenta la longitud d de cada ciclo, observamos que coincide el contaje de iteraciones con los valores de la fórmula anterior, mostrado en la tabla siguiente separándolos con "#":

Pero como esa situación nos es realista, acotamos para el máximo para d = n-k no eliminando la sentencia iter += cycle.length, con lo que nos queda la expresión final siguiente para el algoritmo permuteCycles1(list, k) que genera las permutaciones cíclicas, siendo una cota superior:

Estos son los valores para el contaje de iteraciones y los obtenidos con esa fórmula:

En ese coste ya se incluye el coste de copiar los subresultados.

Insertando un elemento en un array: uso de toSpliced()

Ya vimos el método de Array splice() para eliminar elementos y/o insertar nuevos. Tal como vimos en un tema anterior sobre el uso de métodos de Array en recursivos, splice() modifica el propio Array y en ciertos casos como en recursivos nos interesa que cree un nuevo array, para lo cual se ha agregado a JavaScript el nuevo método toSpliced(start, num, "a", "b", ...) con los mismos argumentos, insertándose en la posición start, eliminando num elementos (si es cero se insertan sin eliminar) e insertando el resto de argumentos "a", "b", ... que pueden ser de cualquier tipo aunque ahí los expresemos como string.

Como pusimos en un comentario del algoritmo, el uso de toSpliced

arr[i] = cycle.toSpliced(j, 0, pivot)

es equivalente a usar slice() y el operador de propagación ...:

arr[i] = [...cycle.slice(0, j), pivot, ...cycle.slice(j)]

Ambos tienen el mismo coste que es la longitud del array cycle si tenemos en cuenta que estamos insertando pivot que es una constante de un único elemento siempre.

Segundo algoritmo para generar permutaciones cíclicas

Implementamos un segundo algoritmo con la recurrencia que vimos en [2]:

//S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1)
function permuteCycles2(list=[], k=0) {
    let result = [];
    let n = list.length;
    if (n===k) {
        //iter += n;
        result.push(list.map(v => [v]));
    } else if (n===0 || k===0 || n<k) {
        //iter += 1;
        result = [];
    } else if (k===1) {
        //iter += 1;
        let pivot = list[0];
        //iter += n-1;
        let sublist = list.slice(1);
        let p = permute3(sublist);
        /* p.length = (n-1)! */
        for (let j=0; j<p.length; j++){
            /* p[j].length = n-1 */
            //iter += 1 + p[j].length;
            result.push([[pivot, ...p[j]]])
        }
    } else {
        //iter += 1;
        let pivot = list[0];
        //iter += n-1;
        let sublist = list.slice(1);
        let res = permuteCycles2(sublist, k-1);
        /* res.length = S(n-1, k-1) */
        for (let p of res) {
            /* p.length = k-1 */
            //iter += 1 + p.length;
            result.push([[pivot], ...p]);
        }
        res = permuteCycles2(sublist, k);
        for (let p of res) {
            /* p.length = k ciclos */
            //iter += 1;
            for (let i=0; i<p.length; i++) {
                //iter += 1;
                let cycle = p[i];
                /* cycle.length promedio =  (n-1)/k */
                for (let j=0; j<cycle.length; j++) {
                    //iter += 1;
                    /* coste copia = k+(n-1) */
                    //iter += p.length + p.reduce((q,v) =>
                    //       (q+=v.length, q), 0);
                    let arr = copy2(p);
                    //iter += cycle.length;
                    /* es lo mismo que [...cycle.slice(0, j),
                       pivot, ...cycle.slice(j)] */
                    arr[i] = cycle.toSpliced(j, 0, pivot);
                    result.push(arr);
                }
            }
        }
    }
    return result;
}

Ejecutando el algoritmo en la herramienta Combine Tools para el conjunto abcd con k=2, obtenemos las siguientes S(4, 2) = 11 permutaciones cíclicas:

El siguiente esquema presenta la evolución del algoritmo. Los círculos con un número en su interior representan la llamada inicial con un 0, la primera llamada a permuteCycles2(sublist, k-1) y la segunda llamada a permuteCycles2(sublist, k). Con un fondo negro representan los retornos de esas llamadas, tras lo cual se recomponen los resultados. Los textos en verde son las devoluciones de los casos bases:

0⇒ S(abcd, 2) ⇒
pivot=a sublist=bcd ⇒
1⇒ S(bcd, 1) = (bcd),(bdc) 1⇒ (a)(bcd), (a)(bdc)
2⇒ S(bcd, 2) ⇒
    pivot=b sublist=cd ⇒
    1⇒ S(cd, 1) = (cd) 1⇒ (b)(cd) 2⇒ (ab)(cd), (b)(acd), (b)(cad)
    2⇒ S(cd, 2) = (c),(d) 2⇒ (bc)(d), (c)(bd) 2⇒ (abc)(d),(bac)(d),
         (bc)(ad), (ac)(bd), (c)(abd), (c)(bad)
0⇒ (a)(bcd), (a)(bdc), (ab)(cd), (b)(acd), (b)(cad), (abc)(d),
     (bac)(d), (bc)(ad), (ac)(bd), (c)(abd), (c)(bad)

Observe que este esquema es más escueto que el que vimos para el algoritmo anterior, pues evitamos llegar al caso base k=0. En principio esto parece que reduce el coste, pero como veremos al final de hecho no se reduce tanto, pues la reducción por ese concepto se contraresta con el coste de permutar en el caso base k=1.

La recurrencia del coste planteada es igual que la del primer algoritmo a excepción de que ahora agregamos el caso base k=1, en cuyo caso el coste es T_p(n-1), coste del algoritmo permute3(list)

Como antes, seguimos sin conocer d con exactitud:

Con d=0 y eliminando la sentencia iter += cycle.length, vemos que el contaje de iteraciones y la fórmula producen el mismo valor:

Y dado que 1 ≤ d ≤ n-k acotamos el coste tomando el valor máximo d = n-k como hicimos para el primer algoritmo, con lo que nos queda la expresión final siguiente para el algoritmo permuteCycles2(list, k) que genera las permutaciones cíclicas.

En un caso base tenemos T_p(n) como el coste del algoritmo permute3(list):

El comparativo entre el contaje de iteraciones y la fórmula es el siguiente, observando que es una cota superior en todos los casos:

En caso de copia se agrega lo resaltado en amarillo.

Tercer algoritmo para generar permutaciones cíclicas

El tercer algoritmo para generar permutaciones cíclicas se basa en la recurrencia que vimos en [3]:

Esta recurrencia que utiliza los números de Stirling de primera clase es parecida a la que vimos para implementar el Segundo algoritmo para generar particiones parciales que utilizaba la recurrencia S2(n, k) = ∑_j=k-1..n-1 S2(j, k-1) C(n-1, j) basada en los números de Stirling de segunda clase, cuya implementación me resultó mucho más sencilla que la de este apartado. Empecemos viendo el algoritmo:

// S(n, k) = sum_(j=k-1)^(n-1) S(n-1, j) C(j, k-1)
function permuteCycles3(list=[], k=0, n0=list.length, k0=k) {
    let result = [];
    let n = list.length;
    if (n===k) {
        //iter += n;
        result.push(list.map(v => [v]));
    } else if (n===0 || k===0 || n<k) {
        //iter += 1;
        result = [];
    } else {
        //iter += 1;
        let pivot = list[list.length-1];
        //iter += (n-1);
        let subList = list.slice(0, list.length-1);
        for (let j=k-1; j<=n-1; j++) {
            //iter += 1;
            let p = permuteCycles3(subList, j, n0, k0);
            //iter += j;
            let subList2 = Array.from({length: j}, (v,i) => i);
            let c = combine2(subList2, k-1);
            for (let m=0; m<p.length; m++) {
                //iter += 1;
                let res = p[m];
                for (let i=0; i<c.length; i++) {
                    //iter +=1;
                    if (j>k) {
                        let arr = [];
                        let arrp = [];
                        for (let ii=j-1; ii>-1; ii--) {
                            //iter += 1;
                            /* c[i].includes(ii) */
                            if (includesNumber(c[i], ii)) {
                                arr.push(res[ii]);
                            } else {
                                arrp.push(...res[ii]);
                            }
                        }
                        arrp.push(pivot);
                        arr.push(arrp);
                        if (n===n0 && k===k0) {
                            result.push(arr);
                        } else {
                            result.push(canonizePermuteCycles(arr));
                        }
                    } else if (j===k) {
                        let cycle = 0;
                        for (let ii=0; ii<j; ii++) {
                            //iter += 1;
                            /* !c[i].includes(ii) */
                            if (!includesNumber(c[i], ii)) {
                                cycle = ii;
                                break;
                            }
                        }
                        res[cycle].push(pivot);
                        //iter += n+k;
                        result.push(copy2(res));
                        res[cycle].pop();
                    } else  {
                        res.push([pivot]);
                        //iter += n+k;
                        result.push(copy2(res));
                        res.pop();
                    }
                }
            }
        }
    }
    return result;
}

En el algoritmo anterior necesitamos las funciones auxiliares includesNumber(), canonizePermuteCycles() y cyclesSort():

function includesNumber(numbers=[], number=-1) {
    for (let i=0; i<numbers.length; i++){
        //iter += 1;
        if (numbers[i]===number){
            return true;
        }
    }
    return false;
}

function canonizePermuteCycles(cycles=[]){
    for (let i=0; i<cycles.length; i++) {
        //iter += 1;
        let n = cycles[i].length;
        if (n===2 && cycles[i][0]>cycles[i][1]) {
            [cycles[i][0], cycles[i][1]] = [cycles[i][1], cycles[i][0]];
        } else if (n>2) {
            let m = cycles[i][0];
            for (let j=1; j<n; j++){
                //iter +=1;
                if (cycles[i][j]<m) m = cycles[i][j];
            }
            let c = [m];
            while (c.length<n) {
                //iter += 1;
                /* let k = cycles[i].indexOf(m) */
                let k = -1;
                for (let j=0; j<cycles[i].length; j++){
                    //iter += 1;
                    if (cycles[i][j]===m){
                        k = j;
                        break;
                    }
                }
                k = k===n-1 ? 0 : k+1;
                m = cycles[i][k];
                c.push(m);
            }
            cycles[i] = c;
        }
    }
    iter += cycles.length**2;
    /* cycles.sort((v, w) => v[0]<w[0] ? -1 : 1) */
    cyclesSort(cycles);
    return cycles;
}

function cyclesSort(cycles=[]) {
    let n = cycles.length;
    let swap = true;
    while (swap) {
        //iter += 1;
        swap = false;
        for (let i=1; i<n; i++){
            //iter += 1;
            if (cycles[i-1][0]>cycles[i][0]){
                [cycles[i-1], cycles[i]] = [cycles[i], cycles[i-1]];
                swap = true;
            }
        }
        n = n-1;
    }
}

El motivo de includesNumber() es evitar el uso del método [].includes() puesto que necesitamos contar las iteraciones. En una versión en producción debería usarse ese método. La función canonizePermuteCycles(), que explicaremos más abajo, también usa el método [].indexOf(), que para contar iteraciones sustituimos por un bucle. Finalmente el método [].sort() también es sustituido por cyclesSort() para contar las iteraciones, usando el algoritmo de la burbuja que es muy simple, aunque no el más eficiente.

Presentaremos un esquema basado en generar las permutaciones cíclicas con el conjunto o lista a,b,c,d y generando permutaciones con 2 ciclos. En números aplicamos la recurrencia dada S(n, k) = ∑_j=k-1..n-1 S(n-1, j) C(j, k-1) a estos valores:

Observamos que hemos de obtener 11 resultados, tal como se evidencia en los resultados de los números de Stirling de primera clase y de los binomiales:

Antes de ver un esquema de evolución, vemos que n=k ⇒ C(n, k) = 1, n<k ⇒ C(n, k) = 0. Esto quiere decir que C(0, 0) = 1 y k>0 ⇒ C(0, k) = 0. Entonces para k=0 el binomial siempre devuelve al menos un resultado, es decir si M es un conjunto de cero o más elementos, entonces binomial(M, 0) = [∅]

Si en los esquemas que siguen entendemos S(n, k) como el algoritmo permuteCycles3(list, k) que vimos antes y C(n, k) como el algoritmo combine2(list, k), entonces teniendo en cuenta la recurrencia S(n, k) = ∑_j=k-1..n-1 S(n-1, j) C(j, k-1) que estamos aplicando, la lista será {a₁, a₂, ..., a_n-1} para S(n-1, j) y {0, 1, 2, ..., j} para C(j, k-1). Con el ejemplo abcd y k=2 resulta, lo siguiente, recordando que está puesto en forma compacta, pues algo como C(012, 1) realmente se está refieriendo a C({0, 1, 2}, 1):

Así, por ejemplo, S(abc, 3) = (a)(b)(c) es UNA permutación con 3 ciclos, mientras que C(012, 1) = [0],[1],[2] es una lista de TRES combinaciones.

El conjunto {0, 1, 2, ..., j} empieza en cero debido a que serán posiciones de los ciclos de una permutación donde actuar, pues una permutación cíclica como (a)(bcd) se maneja en el código como el array [["a"], ["b", "c", "d"]]. Así la posición 0 es el ciclo ["a"] y la posición 1 es el ciclo ["b", "c", "d"]. Teniendo en cuenta esto, el primer esquema de llamadas y retornos de casos bases es el siguiente:

S(abcd, 2)
    S(abc, 1) × C(0, 1)
        S(ab, 0) × C(∅, 0) ⇒ caso base k=0 ⇒ ∅ × [∅]
        S(ab, 1) × C(0, 0)
             S(a, 0) × C(∅, 0) ⇒ caso base k=0 ⇒ ∅ × [∅]
             S(a, 1) × C(0, 0) ⇒ caso base n=k ⇒ (a) × [∅]
        S(ab, 2) C(01, 0) ⇒ caso base n=k ⇒ (a)(b) × [∅]
    S(abc, 2) C(01, 1)
        S(ab, 1) × C(0, 1)
             S(a, 0) × C(∅, 0) ⇒ caso base k=0 ⇒ ∅ × [∅]
             S(a, 1) × C(0, 0) ⇒ caso base n=k ⇒ (a) × [∅]
        S(ab, 2) × C(01, 1) ⇒ caso base n=k ⇒ (a)(b) × [0],[1]
    S(abc, 3) C(012, 1) ⇒ caso base n=k ⇒ (a)(b)(c) × [0],[1],[2]

Recordando que hemos de obtener estos resultados para el ejemplo dado:

veamos el esquema completo:

S(abcd, 2)
    k=2, pivot=d
    S(abc, 1) × C(0, 1) = S(abc, 1) × [∅]
        k=1, pivot=c
        S(ab, 0) × C(∅, 0) ⇒ ∅ × [∅] ⟶ ∅ × [∅] = ∅
        S(ab, 1) × C(0, 0) = S(ab, 1) × [∅]
            k=1, pivot=b
            S(a, 0) × C(∅, 0) ⇒ ∅ × [∅] ⟶ ∅ × [∅] ⟶ ∅ × [∅] = ∅
            S(a, 1) × C(0, 0) ⇒ (a) × [∅] j=1=k=1;b ⟶
                ⟶ (ab) × [∅] j=1=k=1;c ⟶
                ⟶ (abc) × [∅] j=1<k=2;d = (abc)(d)
        S(ab, 2) C(01, 0) ⇒ (a)(b) × [∅] j=2>k=1;c ⟶
            ⟶ (bac) ≡ (acb) × [∅] j=1<k=2;d = (acb)(d)
    S(abc, 2) C(01, 1) = S(abc, 2) × [0],[1]
        k=2, pivot=c
        S(ab, 1) × C(0, 1) = S(ab, 1) × [0]
             k=1, pivot=b
             S(a, 0) × C(∅, 0) ⇒ ∅ × [∅] ⟶ ∅ × [0] ⟶ ∅ × [0],[1] = ∅
             S(a, 1) × C(0, 0) ⇒ (a) × [∅] j=1=k=1;b ⟶
                ⟶ (ab) × [0] j=1<k=2;c ⟶
                ⟶ (ab)(c) × [0],[1] ⟶
                    · (ab)(c) × [0] j=2=k=2;d = (ab)(cd)
                    · (ab)(c) × [1] j=2=k=2;d = (abd)(c)
        S(ab, 2) × C(01, 1) ⇒ (a)(b) × [0],[1] j=2=k=2;c ⟶
            ⟶ (a)(bc), (ac)(b) × [0],[1] ⟶
                · (a)(bc) × [0] j=2=k=2;d = (a)(bcd)
                · (a)(bc) × [1] j=2=k=2;d = (ad)(bc)
                · (ac)(b) × [0] j=2=k=2;d = (ac)(bd)
                · (ac)(b) × [1] j=2=k=2;d = (acd)(b)
    S(abc, 3) C(012, 1) ⇒ (a)(b)(c) × [0],[1],[2] ⟶
        · (a)(b)(c) × [0] j=3>k=2;d = (a)(cbd) ≡ (a)(bdc)
        · (a)(b)(c) × [1] j=3>k=2;d = (b)(cad) ≡ (b)(adc)
        · (a)(b)(c) × [2] j=3>k=2;d = (c)(bad) ≡ (c)(adb)

En color azul vemos los resultados finales que coinciden con los esperados.

Los retornos de los casos bases se presentan con una flecha doble resaltada amarillo. Vea que el primero ⇒ ∅ × [∅] ⟶ ∅ × [∅] = ∅ no devuelve ningún resultado, pues aunque ya vimos que C(∅, 0) = [∅] devuelve un elemento (un Array con el elemento vacío), en cambio S(ab, 0) = ∅ devuelve cero elementos (no devuelve ningún Array). Al "multiplicar" o componer 0×1=0obtenemos cero resultados.

En uno de los primeros retornos vemos ⇒ (a) × [∅] j=1=k=1;b ⟶ (ab), siendo j=1 dado que tenemos un único ciclo (a) y k=1, entonces como j=k estamos en la alternativa else if (j===k) del algoritmo. Como tenemos los ciclos que se precisan en ese momento, sólo tenemos que añadir el pivote pivot=b al único ciclo existente quedando (ab).

El primer resultado finaliza con ⟶ (abc) × [∅] j=1<k=2;d = (abc)(d), teniendo otra vez un único ciclo (abc) con lo que j=1, pero ahora k=2, con lo que j<k y estamos en la alternativa else del algoritmo, es decir, hay menos ciclos (j=1) que los requeridos en ese momento (k=2), con lo que agregamos el pivote d como ciclo al final quedando (abc)(d) que es el primer resultado que se obtiene.

La otra alternativa if (j>k) del algoritmo la vemos en el retorno ⇒ (a)(b) × [∅] j=2>k=1;c ⟶ (bac) ≡ (acb) donde tenemos j=2 ciclos y sólo necesitamos k=1 ciclo, así que tenemos que borrar uno e incorporar sus elementos a los otros ciclos y el pivote c, con lo que obtenemos bac. En esta parte hemos de canonizar la permutación cíclica, lo que representamos con (bac) ≡ (acb) para que esté en el orden correcto para lo retornos siguientes.

En lo anterior teníamos [∅] como resultado de las combinaciones, que al igual que con [0] multiplica por un resultado binomial. En otro caso como ⇒ (a)(b) × [0][1] j=2=k=2;c ⟶ (a)(bc), (ac)(b) vemos que (a)(b) (1 permutación) multiplicado por [0],[1] (2 resultados binomiales) produce 1×2=2 resultados (a)(bc), (ac)(b) pues se aplica (a)(b) × [0] (agregando el pivote al segundo ciclo) y a continuación (a)(b) × [1] (agregando el pivote al primer ciclo), con lo que [0],[1] viene a ser las posiciones de los ciclos que hay que mantener sin modificar.

Canonizar permutaciones cíclicas

En el tema siguiente exponemos una Calculadora de permutaciones cíclicas. Una de las operaciones que podemos hacer es obtener la forma canónica de una permutación cíclica. Por ejemplo, la permutación (5 3)(4 1 2) se canoniza como (1 2 4)(3 5), ordenando los ciclos por su primer elemento y, dentro de cada ciclo, disponemos el ordenamiento correspondiente al que tenga el primer menor elemento.

En el algoritmo, en la alternativa if (j>k) es necesario canonizar cada subresultado para que, al servir de entrada a una subsiguiente llamada, esté en el orden correcto. Sin embargo no es necesario devolver los últimos resultados canonizados. Por eso hemos dispuesto en el código de los argumentos n0 y k0 que toman los valores iniciales:

function permuteCycles3(list=[], k=0, n0=list.length, k0=k) {
    ...
    let p = permuteCycles3(subList, j, n0, k0);
    ...
    if (n===n0 && k===k0) {
        result.push(arr);
    } else {
        result.push(canonizePermuteCycles(arr));
    }
...

Cuando almacenemos un resultado sabremos si es un resultado final cuando n===n0 && k===k0, en cuyo caso no lo canonizamos pues esta parte tiene un coste considerable, como se observa en esta tabla de costes sin y con esta mejora para k=2:

Coste del tercer algoritmo

No me ha sido fácil determinar el coste con exactitud, debido a la ejecución donde entran en juego las funciones auxiliares includesNumber(), canonizePermuteCycles() y cyclesSort(). Por lo tanto lo que sigue es una estimación de una cota superior para valores de n, k que puedo ejecutar en mi ordenador. El resultado mediante fórmula recurrente que sigue las sentencias Iter que cuenta iteraciones en el algoritmo es el siguiente:

Siendo S(n-1, j) los números de Stirling de primera clase que se calcula con la recurrencia que también sirve de base al algoritmo

Por otro lado T_c(j, k-1) el coste del algoritmo combine2(list, k) con este coste, agregándose lo resaltado en amarillo en caso de coste con copia (para el resto el coste es el mismo dado que siempre hay que copiar resultados parciales):

Además tenemos la variable q como estimación correspondiente a las alternativas j>k, j===k, j<k del cuerpo central del algoritmo, pues incluye bucles interiores que usan la función includesNumber() y canonizePermuteCycles() de las que no he podido determinar el coste exacto, razón por la cual el coste final es una cota superior estimada. El coste desconocido lo estimamos en función de j²+r para la primera alternativa y j² para la segunda, donde el coste de copiar los resultados parciales en las dos últimas alternativas es n+k.

donde a su vez r es otra estimación del coste de la función para canonizar los resultados finales con la función canonizePermuteCycles(), siendo cero con n₀, k₀ los valores iniciales en la ejecución del algoritmo y en otro caso se estima en (n-k)².

Vemos que esta fórmula supone una cota superior al menos para valores hasta 10 que es lo máximo que podemos generar en la aplicación sin que el navegador colapse y con un límite inferior a 5×10⁷ iteraciones (50 millones iteraciones):

Comparativo de costes de los tres algoritmos

El ahorro de coste del segundo algoritmo con respecto al primero no es muy significativo, como se observa en esta tabla de primeros valores con k=2. El tercer algoritmo tiene el peor coste, incluso con la mejora de no canonizar los últimos resultados: