Combinatoria con recursivos

Combinatoria

Configuración
La función para copiar Arrays puede afectar al tiempo de ejecución. Puede cambiar el método de copia en la configuración.
Vista del resultado

Combinaciones

Las combinaciones de una lista con n elementos son todas las sublistas con k elementos distintos que se pueden extraer sin importar el orden. Se denotan como (nk), C(n, k) y también como Cn,k.

Número de sublistas:
C(n, k) =n!
k!(n-k)!
Base matemática:
C(n, k) = C(n-1, k-1) + C(n-1, k)
Sublistas generadas:
Tiempo:
Iteraciones: (Sin coste de copia)
Coste calculado (Sin coste de copia):
T(n, k) = 2 ( ∑j=0..k C(n, j) ) - 1 =
Código JS: Llamar con combine1(list, k)
// C(n, k) = C(n-1, k-1) + C(n-1, k)
function combine1(list=[], k=0, n=list.length, res=[], result=[], n0=list.length){
    if (k===0){
        result.push(copy(res));
    } else if (n>0) {
        res.push(list[n0-n]);
        combine1(list, k-1, n-1, res, result);
        res.pop();
        combine1(list, k, n-1, res, result);
    }
    return result;
}
Trazado
Versión: 2023-05-28

Aplicación Combinatoria

Figura
Figura. Combinatorics Tool

La combinatoria estudia la forma de generar todas las posibles sublistas de una lista de elementos. En el fondo se trata de contar elementos. Los métodos principales son las combinaciones, permutaciones y variaciones de una lista de elementos. Vea que el problema es generar el conjunto de sublistas más que calcular el valor númerico de esas funciones. Ya hace tiempo analicé el coste de permutar un Array. En esa serie de temas veíamos como resolver recurrencias para calcular el coste de algoritmos recursivos usando técnicas como el desarrollo o la ecuación característica. A raíz de necesitar las combinaciones de una lista de dígitos para la aplicación Sudoku, me planteé estudiar más a fondo estas funciones combinatorias.

Para analizar las combinaciones C(n, k) hemos de utilizar la técnica de la función generadora o generatriz, pues al tener dos variables no parece que puedan usarse las otras técnicas para resolverlo. Esta aplicación servirá para comprobar los resultados matemáticos alcanzados en cada caso. Con esta aplicación se incluyen una serie de temas que analizan el coste de las funciones combinatorias. El primer tema Funciones de generación para resolver recurrencias es una introducción a esa materia, repitiendo algunos problemas que ya resolvimos con desarrollos o ecuación característica.

Para cada método se incluyen uno o más algoritmos, principalmente usando recursivos. A continuación se muestra una lista de funciones que actualmente se ofrecen en la aplicación. Por cada función se incluye la descripción de la función, la fórmula para calcular el valor numérico y una lista de algoritmos. En cada uno tenemos unos enlaces a temas, la recurrencia matemática en la que se basa el algoritmo, el coste sin copia de resultados T y el coste con copia T'. Esta lista será actualizada cada vez que modifique o agregue un nuevo algoritmo. Aquellas que tienen un enlace a un tema son las que he analizado el coste. Los algoritmos sin analizar puede que no sean los más eficientes o necesiten mejoras, por lo que podrán ser modificados.

  • Combinaciones C(n, k)

    Las combinaciones sin repetición de una lista con n elementos distintos son todas las sublistas con k elementos distintos que se pueden extraer sin importar el orden. Se denotan como (nk), C(n, k) y también como Cn,k.

    C(n, k) =n!=
    k!(n-k)!

  • Combinaciones con repetición CR(n, k)

    Las combinaciones con repetición de una lista con n elementos distintos son todas las sublistas con k elementos no necesariamente distintos que se pueden extraer sin importar el orden. Se denotan como ((nk)), CR(n, k) y también como CRn,k.

    CR(n, k) = C(n+k-1, k) =(n+k-1)!=
    k!(n-1)!

  • K-Tuplas K(n, k)

    Las K-Tuplas de un conjunto A con n elementos distintos son todas las sublistas ordenadas que podemos generar con las permutaciones aplicadas sobre todos los subconjuntos de orden k hasta n que se obtienen desde el conjunto A.

    K(n, k) = ∑j=0..n-kn! =
    j!

    • kTuples1(list)
      • K-Tuplas (1)
      • K(n, k) = ∑j=k..n C(n, j) P(j)
      • T(n, k) = 1 + ∑j=k..n ( 1 + TC2(n, j) + C(n, j) ( 1 + j + TP2(j) ) )
      • T'(n, k) = 1 + ∑j=k..n ( 1 + T'C2(n, j) + C(n, j) ( 1 + j + T'P2(j) ) )
      • Donde TC2 es el coste del algoritmo combine2 y TP2 es el del algoritmo permute2 sin coste de copia. Y T'C2 y T'P2 son los costes con copia.

  • Permutaciones P(n)

    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). Matemáticamente es preferible P(n, k), 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 aquí vamos a considerar las permutaciones de forma separada de la variaciones.

    P(n) = n! =

    • permute1(list)
      • Permutar un Array con un recursivo
      • Combinatoria: Permutaciones
      • P(n) = n! = n × (n-1)! = n × P(n-1)
      • T(n) = Max ( 1, n! (n2+n-5+ ∑j=3..nj2+j+1) )
        2j!
      • T'(n) = Max ( 1, n! (n2+n-5+ ∑j=3..nj2+j+1) )
        2j!
      • Un segundo valor se obtiene de la segunda forma equivalente:
        T(n) = Max ( 1, n! (n2+n-n+3+ 4 ∑j=3..n1) )
        2n!j!
        Este algoritmo reduce la lista inicial con slice(), por lo que no modifica la lista inicial. Produce siempre resultados parciales que no son necesarios copiarlos, por lo que la configuración con y sin copia de resultados parciales produce el mismo coste.
    • permute2(copy(list))
      • Permutar con el Algoritmo de Heap
      • Combinatoria: Permutaciones de Heap
      • Heap: P(n) = n! = n × (n-1)! = n × P(n-1)
      • T(n) = 1 + 2 ∑j=2..nn!
        (n-j+1)!
      • T'(n) = n n! + 1 + 2 ∑j=2..nn!
        (n-j+1)!
      • Un segundo valor se obtiene de la segunda forma equivalente (con coste de copia hay que sumar n×n!):
        T(n) = 2n! - 1 + 2 ∑j=2..nn!
        j!
        Este algoritmo modifica la posición de los elmentos de la lista inicial, por lo que si no desea modificarla debe llamarse con permute2(copy(list)). Este coste de copia inicial no se contempla en el cálculo del coste.
    • permute3(list)
      • Permutar con el Algoritmo de Heap
      • Combinatoria: Permutaciones de Heap
      • Heap-2: P(n) = n! = n × (n-1)! = n × P(n-1)
      • T(n) = 1 + 2 ∑j=2..nn!
        (n-j+1)!
      • T'(n) = n n! + 1 + 2 ∑j=2..nn!
        (n-j+1)!
      • Un segundo valor se obtiene de la segunda forma equivalente (con coste de copia hay que sumar n×n!):
        T(n) = 2n! - 1 + 2 ∑j=2..nn!
        j!
        Este algoritmo modifica la posición de los elmentos de la lista inicial, por lo que si no desea modificarla debe llamarse con permute3(copy(list)). Este coste de copia inicial no se contempla en el cálculo del coste.

  • Permutaciones con repetición PR(r1, ..., rm)

    Permutaciones con repetición de una lista A = { a1, ..., an }, donde al quitar los elementos repetidos obtenemos la lista { b1, ..., bm } con m≤n elementos distintos, donde cada elemento bi puede estar repetido ri veces, de tal forma que r1+...+rm = n, son todas las posibles ordenaciones de la lista A. Se denota como PR(r1, ..., rm).

    PR( r1, ..., rm ) =( r1 + ... + rm )!=
    r1! × ... × rm!

    • permuteR1(list)

    • Variaciones V(n, k)

      Las variaciones sin repetición de una lista con n elementos distintos son todas las sublistas ordenadas con k elementos distintos que se pueden extraer. Se denota como V(n, k). Las variaciones es un concepto que matemáticamente se considera como un caso particular de las permutaciones P(n, k) = n! / (n-k)!, denominadas como permutación parcial o k-permutación, con k≤n, siendo P(n, n) = n! / (n-n)! = n! Pero dado que aún sigue apareciendo como una figura distinta, mantenemos las variaciones en un apartado diferenciado de las permutaciones.

      V(n, k) = C(n, k) P(k, k) = C(n, k) k! =n!=
      (n-k)!

      • vary1(list, k)
        • V(n, k) = C(n, k) × P(k)
        • T(n, k) = 1 + TC1(n, k) + C(n, k) × (1 + TP1(k))
        • T'(n, k) = 1 + TC1(n, k) + C(n, k) × (1 + TP1(k))
        • Donde TC1(n, k) es el coste del algoritmo combine1 y TP1(k) es el del algoritmo permute1, tanto con o sin coste de copia.
      • vary2(list, k)
        • V(n, k) = C(n, k) × P(k) = (C(n-1, k-1) + C(n-1, k)) × P(k)
        • T(n, k) = 2 (1+TP1(k)) ( ∑ j=0..k C(n, j) ) - 1 - TP1(k) ∑ j=0..k C(n+1, j)
        • T'(n, k) = 2 (1+TP1(k)) ) ∑ j=0..k C(n, j) ) - 1 - TP1(k) ∑ j=0..k C(n+1, j)
        • Donde TP1(k) es el coste del algoritmo permute1, tanto con o sin coste de copia.
      • vary3(list, k)
        • V(n, k) = n × V(n-1, k-1)

    • Variaciones con repetición VR(n, k)

      Las variaciones con repetición de una lista con n elementos distintos son todas las sublistas ordenadas con k elementos no necesariamente distintos que se pueden extraer. Se denota como VR(n, k).

      VR(n, k) = nk =

      • varyR1(list, k)
        • VR(n, k) = nk = n × nk-1 = n × VR(n, k-1)