Primer algoritmo mejorado para generar particiones

En el primer algoritmo partition1(list) que vimos en el tema anterior necesitábamos las combinaciones y sus complementarias, lo que hacíamos usando dos veces el algoritmo combine2(list, k), una para las combinaciones y otra para las complementarias. Para evitar este doble coste ideamos el algoritmo combineComplement1(list, k) que nos permite obtener ambos resultados en una única ejecución, reduciendo significativamente el coste.

Recordemos que combineComplement1(list, k) nos devolvía un Array donde cada elemento es a su vez un Array, con la primera posición el resultado de la combinación y el segundo la de su complementario.

Con eso el primer algoritmo mejorado partition2(list) que presentamos a continuación para generar las particiones es igual que el del tema anterior partition1(list), variando sólo lo comentado sobre la obtención de las combinaciones y sus complementarias usando combineComplement1(list, k):

// n≤2 ⇒ B(n)=1, B(n) = sum_(j=0)^(n-1) C(n-1, j) B(j)
function partition2(list=[]){
    let n = list.length;
    let result = []
    if (n===0) {
        //iter += 1;
        result.push([]);
    } else if (n===1) {
        //iter += 1;
        result.push([[list[0]]]);
    } else if (n===2) {
        //iter += 1;
        result.push([[list[0], list[1]]], [[list[1]], [list[0]]]);
    } else {
        //iter += 1;
        //iter += (n-1);
        let subList = list.slice(1);
        let pivot = list[0];
        for (let j=0; j<=n-1; j++) {
            //iter += 1;
            let c = combineComplement1(subList, j);
            for (let i=0; i<c.length; i++) {
                //iter += 1;
                let [combination, complement] = c[i];
                /* complement.length = n-1-j */
                //iter += complement.length;
                let pc = [pivot, ...complement];
                let p = partition2(combination);
                /* p.length = bell(j) */
                for (let k=0; k<p.length; k++) {
                    //iter += 1;
                    p[k].push(pc);
                    result.push(p[k]);
                }
            }
        }
    }
    return result;
}

El desglose del coste algoritmo partition1(list) visto en el tema anterior es igual al de este algoritmo, variando sólo el coste de obtener las combinaciones y sus complementarias que denominaremos T_cc(n, k):

Simplificando la parte recursiva

Aplicando el sumatorio a cada término posible, sabiendo que

• ∑_j=0..n-1 1 = n
• ∑_j=0..n-1 C(n-1, j) (n-j) = (n+1) 2^n-2
  Puede comprobarse en WolframAlpha
• ∑_j=0..n-1 C(n-1, j) B(j) = B(n)
  Por definición del número de Bell como vimos en el tema anterior.
• Por otro lado recordando el coste del algoritmo combineComplement1(list, k) de las combinaciones complementarias era
  T_cc(n, k) = 2 C(n+1, k) - 1 + n k C(n, k) + k
  que aplicando a lo anterior tenemos
  ∑_j=0..n-1 T_cc(n-1, j) = ∑_j=0..n-1 ( 2 C(n, j) - 1 + (n-1) j C(n-1, j) + j ) =

  = 1/4 (2(n-4)(n+1) + 2ⁿ((n-2)n+9))
  Puede verlo en WolframAlpha

Agrupando todo lo anterior y simplificando, llegamos a lo siguiente, donde se incluye el sumatorio sólo al término con T(j):

Incluyendo las condiciones iniciales, esta es la fórmula del coste del algoritmo partition2(list):

Recordemos que B(n) son los números de Bell, para lo cual no hay una fórmula cerrada, calculándose con la recurrencia:

Si incorporamos el coste de copia, sólo hemos de tenerlo en cuenta para combineComplement1(list, k) que obteníamos agregando lo resaltado en amarillo en lo que sigue:

Por lo tanto sólo tenemos que agregar a la fórmula sin coste este sumatorio:

Que sumado al término (n²-n+10) 2^n-2 de la fórmula sin coste llegamos a la solución con coste de copia para partition2(list):

Segundo algoritmo mejorado para generar particiones

Para el segundo algoritmo usaremos la versión mejorada para obtener las combinaciones y sus complementarias con combineComplement2(list, k):

// n≤2 ⇒ B(n)=1, B(n) = sum_(j=0)^(n-1) C(n-1, j) B(j)
function partition3(list=[]){
    let n = list.length;
    let result = []
    if (n===0) {
        //iter += 1;
        result.push([]);
    } else if (n===1) {
        //iter += 1;
        result.push([[list[0]]]);
    } else if (n===2) {
        //iter += 1;
        result.push([[list[0], list[1]]], [[list[1]], [list[0]]]);
    } else {
        //iter += 1;
        //iter += (n-1);
        let subList = list.slice(1);
        let pivot = list[0];
        for (let j=0; j<=n-1; j++) {
            //iter += 1;
            let c = combineComplement2(subList, j);
            for (let i=0; i<c.length; i++) {
                //iter += 1;
                let [combination, complement] = c[i];
                /* complement.length = n-1-j */
                //iter += complement.length;
                let pc = [pivot, ...complement];
                let p = partition3(combination);
                /* p.length = bell(j) */
                for (let k=0; k<p.length; k++) {
                    //iter += 1;
                    p[k].push(pc);
                    result.push(p[k]);
                }
            }
        }
    }
    return result;
}

El desglose del coste es igual que en el caso del apartado anterior:

que simplificando queda la parte recursiva:

Aplicando sumatorios a todos los términos menos los que contienen T_cc y T(j) tenemos.

• ∑_j=0..n-1 1 = n
• ∑_j=0..n-1 C(n-1, j) (n-j) = (n+1) 2^n-2
• ∑_j=0..n-1 C(n-1, j) B(j) = B(n)

Con lo que llegamos finalmente a esta fórmula final para el coste de partition3(list)

Donde B(n) son los números de Bell, para lo cual no hay una fórmula cerrada, calculándose con la recurrencia:

Y T_cc(n, k) son las combinaciones complementarias del algoritmo combineComplement2(n, k) para lo que no he encontrado una fórmula cerrada:

En caso de coste de copia sólo hay que agregar lo resaltado en amarillo.

Comparando algoritmos para generar particiones

Comparamos coste de los tres algoritmos vistos para generar particiones: partition1(list) en el tema anterior y partition2(list) y partition3(list) en este tema:

Vemos que el último es el de mejor comportamiento aunque por poca diferencia respecto al primero. En el tema siguiente veremos otro que incluso lo mejora.