Las combinaciones complementarias

Ya vimos en uno de los primeros temas que el número de combinaciones sin repetición de n elementos distintos en subconjuntos de k elementos son las posibles muestras de k elementos distintos y sin orden que pueden extraerse de los n elementos. El número de subconjuntos S de orden k que se obtienen son las combinaciones C(n, k).

Si partimos del conjunto A con n elementos y S_i,k designa uno de esos subconjuntos con 1 ≤ i ≤ C(n, k), entonces A - S_i,k es el subconjunto complementario de combinaciones. Todos los subconjuntos complementarios conforman entonces las combinaciones complementarias de orden k del conjunto A con n elementos.

Las vamos a denotar como C_c(n, k), siendo obvio que el número de subconjuntos es el mismo, es decir, C(n, k) = C_c(n, k), puesto que las combinaciones responden a C(n, k) y las complementarias a C(n, n-k), pero son iguales puesto que:

Ya vimos en uno de los primeros temas el algoritmo combine2(list, k) que nos permitía generar las combinaciones. Por ejemplo, si partimos del conjunto A = {a, b, c} obtenemos estos subconjuntos de combinaciones:

Las combinaciones complementarias se forman incluyendo en cada subconjunto los elementos restantes de A:

Podríamos implementar un algoritmo para generar complement(list, k). Pero si partimos del algoritmo de combine2(list, k) no parece díficil obtener un conjunto de resultados que contenga las combinaciones y sus complementarias, algo como:

Cada subresultado es un Array, como el primero [[a, b], [c]], donde la primera posición [a, b] es una combinación y la segunda [c] es su complementaria. Recuerde que, aunque se usan Arrays, no dejan de ser conjuntos, así que [a, b] es en el fondo el subconjunto {a, b}, donde el orden no importa. Generar combinaciones y complementarias en una misma estructura nos facilitará las cosas cuando veamos algoritmos que implementan las particiones.

Primer algoritmo para implementar combinaciones complementarias

Partimos del algoritmo combine2(list, k) exactamente igual, agregando en el caso base let complement = list.filter(v => !res.includes(v)) para incluir las combinaciones complementarias en cada subresultado:

// C(n, k) = ∑j=k..n C(j-1, k-1)
function combineComplement1(list=[], k=0, n=list.length,
res=Array.from({length:k}, ()==>""), result=[], start=true,
n0=list.length, k0=res.length){
    //if (start) {
    //    iter += k;
    //    start = false;
    //}
    if (k===0){
        //iter += 1 + n0 * k0;
        let complement = list.filter(v => !res.includes(v));
        //if (withCopyCost) iter += res.length;
        result.push([copy(res), complement]);
    } else {
        //iter += 1;
        for (let j=n; j=>=k; j--){
            //iter += 1;
            res[k0-k] = list[n0-j];
            combineComplement1(list, k-1, j-1, res, result, start);
        }
    }
    return result;
}

Para analizar el coste simplemente recordamos el coste del algoritmo de partida combine2(list, k):

Como es el mismo algoritmo, sólo tenemos que añadir el coste de la sentencia let complement = list.filter(v => !res.includes(v)). Si n₀ es la longitud de la lista inicial list y k₀ es la de la sublista inicial res, entonces el coste de esa sentencia es simplemente n₀ × k₀. Como hay C(n, k) subresultados, entonces la fórmula final será la siguiente, generalizado n₀, k₀ como n, k:

En caso de considerar el coste de copia, hay que añadir el coste de copiar los C(n, k) subresultados res cada uno con una longitud k:

Segundo algoritmo para implementar combinaciones complementarias

En esta segunda implementación intentaremos evitar el uso de la sentencia let complement = list.filter(v => !res.includes(v)).

// C(n, k) = ∑j=k..n C(j-1, k-1)
function combineComplement2(list=[], k=0, n=list.length,
res=Array.from({length:k}, ()=>""), resc=[...list], result=[],
start=true, n0=list.length, k0=res.length){
    //if (start) {
    //    iter += n+k;
    //    start = false;
    //}
    if (k===0){
        //iter += 1;
        /*  res.length + resc.length = k + (n-k) = n */
        //if (withCopyCost) iter += res.length + resc.length;
        result.push([copy(res), copy(resc)]);
    } else {
        //iter += 1;
        for (let j=n; j>=k; j--){
            //iter += 1;
            let pivot = list[n0-j];
            res[k0-k] = pivot;
            //iter += resc.length-1; /* = k+n0-k0-1 */;
            resc = resc.slice(1);
            combineComplement2(list, k-1, j-1, res, resc, result, start);
            resc.push(pivot)
        }
    }
    return result;
}

Aparte del subresultado res, un Array de longitud inicial k₀ para generar cada combinación, hemos de incluir otro Array resc para generar cada combinación complementaria, con longitud inicial n₀ pues es una copia de la lista list, donde en cada caso n₀ y k₀ son los valores de la llamada inicial.

En el algoritmo vemos que extraemos el pivote let pivot = list[n0-j], lo mismo que hacíamos con el algoritmo de combine2(list, k). Pero ahora antes de cada llamada reducimos con resc.slice(1) una unidad el subresultado complementario resc y, tras la llamada volvemos a incorporar el pivote con resc.push(pivot). Más abajo veremos algunas consideraciones sobre el uso de métodos como slice() o push() en recursivos.

En cada llamada res se rellena una posición que, con el caso base k===0, alcanza la longitud k₀ posiciones llenas, mientras que resc se decrementa hasta alcanzar la longitud n₀-k₀, pues ambas longitudes sumaran n₀ que es el tamaño de la lista inicial.

Por eso vemos que el coste de reducir resc.slice(1) es resc.length-1 que es lo mismo que k+n₀-k₀-1. Si definimos b = n₀-k₀ que viene a ser constante en el desarrollo de la recurrencia, entonces ese coste es k+b-1.

Observe que no es necesario considerar el caso cuando n<k, pues entonces no se ejecuta el bucle for (let j=n; j>=k; j--), siendo el coste unitario correspondiendo al iter += 1 previo al bucle.

En el siguiente esquema se expone la ejecución del ejemplo combineComplement2([a,b,c], 2) que genera tres subresultados [[a, b], [c]], [[a, c], [b]] y [[b, c], [a]]]:

list=[a,b,c] res=[,] resc=[a,b,c]
call(n=3, k=2)
loop
    j=3 pivot=a res=[a,] slice(1) resc=[b,c]
        call(n=2, k=1)
        loop
            j=2 pivot=b res=[a,b] slice(1) resc=[c]
                call(n=1, k=0) => [[a,b], [c]]
                push(b) resc=[c,b]
            j=1 pivot=c res=[a,c] slice(1) resc=[b]
                call(n=0, k=0) => [[a,c], [b]]
                push(c) resc=[b,c]
        push(a) resc=[b,c,a]
    j=2 pivot=b res=[b,c] slice(1) resc=[c,a]
        call(n=1, k=1)
        loop
            j=1 pivot=c res=[b,c] slice(1) resc=[a]
                call(n=0, k=0) => [[b,c], [a]]
                push(c) resc=[a,c]
        push(b) resc=[c,a,b]

Coste del segundo algoritmo para generar combinaciones complementarias

Vimos la definición de la recurrencia del algoritmo combine2(list, k):

La definición es ahora similar, incoporando k+b-1 que es el coste de reducir una unidad el subresultado complementario resc:

En esta recurrencia diferenciamos t(n, k) de T(n, k), por la necesidad de incorporar el coste inicial n+k que sólo se suma cuando entramos por primera vez en el recursivo. Esto es el coste de componer los arrays res y resc, el primero con longitud k y el segundo con longitud n.

Adelantamos ya que no he podido obtener una fórmula cerrada para calcular el coste. Por lo tanto realizando una aplicación directa de la definición de la recurrencia, tenemos una de las tres soluciones recurrentes finales alternativas que vamos a ofrecer en este tema para el algoritmo combineComplement2(list, k):

Se calcula con este algoritmo:

function t(n, k, b=n-k) {
    if (k===0) {
        return 1;
    } else {
        let sum = 1;
        for (let j=k; j<=n; j++) {
            sum += k + b + t(j-1, k-1, b);
        }
        return  sum;
    }
}

Segunda solución alternativa

Intentaremos ver si podemos eliminar el sumatario, algo parecido a lo que hicimos con la recurrencia de combine2(list, k), partiendo de la recurrencia t(n, k)

Sumamos uno a n y k:

Por lo tanto la recurrencia equivale a esta si volvemos a reducir en una unidad los índices

La recurrencia del algoritmo combine2() era similar sin el término k+b. Allí la resolví usando la técnica de la función generadora. Pero con esta no lo he logrado por ahora. Así que la fórmula final para el algoritmo combineComplement2(list, k) queda, por ahora, así:

En la herramienta Combine Tools usaré el siguiente recursivo para obtener el valor numérico de t(n, k, b), implementando directamente la recurrencia:

function t(n, k, b=n-k) {
    if (k===0 || n<k) {
        return 1;
    } else {
        return k + b + t(n-1, k-1, b) + t(n-1, k, b);
    }
}

Vea que hemos de considerar el caso n<k.

Tercera solución alternativa

Intentemos eliminar el argumento b de la solución recurrente anterior. En primer lugar veamos los primeros valores que se obtienen con esa fórmula:

Si nos centramos en t(n, k):

Entonces los valores de la tabla anterior serían los siguientes, donde en cada celda restamos n+k:

Supongamos ahora que eliminamos el argumento b, que antes era una constante en la evolución de la recurrencia y que tomaba el valor al inicio b = n₀ - k₀. Ahora será variable con valor b = n - k. Denominaremos a esta recurrencia q(n, k):

con la misma definición:

Pero los términos recurrentes los tomaremos de t(n, k):

Usando la tabla de valores que genera la recurrencia [1] desplegaremos valores para esta segunda recurrencia [2]:

Obtenemos cada valor q(n, k) a partir de valores anteriores de t(n, k) que obtenemos de la tabla que se genera a partir de la fórmula [1]. Se observa que las diferencias en cada fila t(n, k) - q(n, k) obedecen al término C(n, k) -1. Entonces, aunque sin demostrar de forma genérica, podemos definir esta solución:

Con lo que tenemos otra solución alternativa para el coste de nuestro algoritmo combineComplement2(n, k)

Usaremos este algoritmo para obtener el valor de t(n, k) en la recurrencia anterior:

function t(n, k) {
    if (k===0 || n<k) {
        return 1;
    } else {
        return n + binomial(n, k) - 1 + t(n-1, k-1) + t(n-1, k);
    }
}

Coste de copiar subresultados

Como vemos en el código del algoritmo cuando llega al caso base

...
if (k===0){
    iter += 1;
    /*  res.length + resc.length = k + (n-k) = n */
    if (withCopyCost) iter += res.length + resc.length;
    result.push([copy(res), copy(resc)]);
} else {
...

en caso de computar el coste de copiar los subresultados, hemos de agregar por cada combinación y su complementaria res.length + resc.length, lo que equivale a k + (n-k) = n, multiplicado por C(n, k) subresultados que se generan. Así que en caso de copia las tres fórmulas quedan así agregando n C(n, k)

Comparando costes de combineComplement1() y combineComplement2()

En la siguiente tabla vemos el coste de combineComplement1(list, 5), combineComplement2(list, 5) así como combine2(list, 5), algoritmo en el que nos basamos para desarrollar los otros dos, usando k = 5 para los primeros valores de n:

• T(n, 5) parar el algoritmo combine2(n, 5)
• T₁(n, 5) parar el algoritmo combineComplement1(n, 5)
• T₂(n, 5) parar el algoritmo combineComplement2(n, 5)

Por supuesto que no alcanzan el mejor coste de combine2, pero a medida que n crece, mayor es el porcentaje de reducción de combineComplement2 respecto a combineComplement1.

Uso de métodos de Array en recursivos

En este apartado exponemos detalles que vimos en un apartado más arriba relacionado con el uso del método slice() de un Array en JavaScript. En el tema métodos para modificar el propio array vimos que eran, entre otros, los siguientes que podríamos encontrar en algoritmos recursivos que manejan arrays:

• let x = arr.push("a") para agregar un elemento al final del array, devolviendo la longitud del array.
• let x = arr.pop() para extrer elemento al final del array, devolviéndolo.
• let x = arr.unshift("a") para agregar un elemento al principio del array, devolviendo su longitud.
• let x = arr.shift("a") para extraer un elemento al principio del array, devolviéndolo.
• let x = arr.splice(start, num, "a", "b", ...) para eliminar num elementos desde la posición start, pudiendo opcionalmente insertarse en esa posición los elementos "a", "b", ... Devuelve un array con los elementos eliminados.
• Hay otros que modifican el propio array, como reverse(), sort(), copyWithin() y fill().

Todos estos métodos modifican el propio array, así que si arr es un array, la sentencia arr.pop() elimina el último elemento, pero lo que devuelve no es el array modificado, sino el elemento eliminado. Por otro lado hay otros métodos para crear nuevos arrays como los siguientes:

• let arr2 = arr.concat("a", "b") concatena al final del array arr los elementos que se le pasan como argumentos. Si se le pasan arrays se concatenarán sus elementos. Devuelve un nuevo array, que podríamos asignar al mismo u a otro nuevo, no modificando el array arr sobre el que se aplica el método. En el fondo está haciendo una copia de arr e insertando al final los nuevos elementos. Es como si utilizáramos el operador de propagación en un nuevo array let arr2 = [...arr, "a", "b"], pues ...arr copia los elementos.
• let arr2 = arr.map(v => v+1) parar iterar por un array que podríamos suponer como arr = [1, 2, 3], devolviendo un nuevo array arr2 = [2, 3, 4] pues suma uno a cada elemento. El array de origen (sobre el que se aplica el método) no se modifica.
• let arr2 = arr.slice(start, end) para recortar un array desde la posición start hasta la posición end, sin incluir esta. Si no se pasa el segundo argumento se entiende que es arr.length, es decir, el final del array. Si por ejemplo arr = [1, 2, 3], entonces let arr2 = arr.slice(1) recortará desde la posición uno devolviendo arr2 = [2, 3]. No modifica el array de origen.
• let arr2 = arr.filter(v => v>1) para filtrar un array, de tal forma que si arr = [1, 2, 3] nos devolverá un nuevo array arr2 = [2, 3]. No modifica el array de origen.

En nuestro algoritmo combineComplement(list, k) teníamos que eliminar el primer elemento del array resc antes de hacer una nueva llamada recursiva, donde pasábamos resc como argumento. Tras la llamada teníamos que insertar el pivote al final de ese array:

resc = resc.slice(1);
combineComplement2(list, k-1, j-1, res, resc, result, start);
resc.push(pivot)
    

Para eliminar el primer elemento, en lugar de usar resc = resc.slice(1), podríamos haber usado resc.shift() o incluso resc.splice(0, 1). Pero no funcionará el recursivo dado que necesitamos crear un nuevo array para pasarlo a la llamada recursiva. Si no lo hacemos así, estaremos pasando la misma referencia en cada llamada. Así que hemos de usar métodos que creen nuevos arrays, como el que usamos resc = resc.slice(1) o incluso resc = resc.filter(v => v!==pivot), pues es precisamente el pivote pivot el que tenemos que eliminar de resc.

Sin embargo la sentencia posterior a la llamada resc.push(pivot) es del tipo que modifica el propio array, pero podemos utilizarlo pues es posterior a la llamada y su estado queda circunscrito a la ejecución en ese momento.

En un tema del año 2016 hice una funcionalidad para mostrar los Métodos de Array existentes en el navegador. En la Figura se observan algunos en color azul con vínculos que llevan a su explicación en otros temas. Pero hay otros nuevos sin vínculos que se han incorporado a JavaScript posteriormente a la publicación de ese tema. Vemos toReversed(), toSorted() y toSpliced().

Precisamente esos que se incorporan son versiones que van a funcionar como el segundo grupo que vimos antes. Así toSpliced() hace lo mismo que splice() pero no modificando el array de origen y devolviendo un nuevo array. En el ejemplo de nuestro algoritmo podríamos también haber usado resc = resc.toSpliced(0, 1).