Combinatoria con recursivos: Combine Tools

Combinatoria: Combine Tools

  
Muestras
El primer valor son las iteraciones y el segundo es el resultado de la fórmula. Ambos deben ser iguales.
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

Factorial

Permutaciones P(n) = n!
0! = 1,
n! = n × (n-1)!
// n! = n * (n-1)!
function factorial(n){
    if (n<=0){
        return 1;
    } else {
        return n*factorial(n-1);
    }
}
Versión: 2024-03-11

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.

Funciones combinatorias

Figura
Figura. Copy Math

El nuevo componente Copy Math nos permite ver la expresión en lenguaje natural de una fórmula. Haciendo doble click (o copiando) una fórmula se abre el panel de Copy Math. Con el botón puede abrir la web Wolfram Alpha para evaluar la expresión.

Si la fórmula contiene valores numéricos, como los que se observan en la Figura, con el botón se puede calcular el resultado que se expone en color azul, como el observado "Resultado cálculo = 4", para lo cual se usa el módulo Calc que ejecuta operaciones para las aplicaciones calculadora y gestor de tablas.

La siguiente tabla resume las funciones combinatorias que he agregado al módulo Calc, exponiendo las que son compatibles para su evaluación en Wolfram Alpha:

TítuloMathResultadoExpresiónExpresión compatible con Wolfram AlphaNotas
Combinaciones (Binomial)
(72)
21C(7, 2)✓
C(n, k) = n! / (k! (n-k)!)
Combinaciones con repetición
((72))
28CR(7, 2)✗
C(7+2-1, 2)
CR(n, k) = C(n+k-1, k)
Permutaciones
P(7)
5040P(7)✗
P(7, 7)
P(n) = n!
Permutaciones
P(7, 7)
5040P(7, 7)✓
P(n, n) = P(n) = n!
Permutaciones
P(7, 2)
42P(7, 2)✓
V(n, k) = P(n, k) = C(n, k) k!
Permutaciones con repetición (Multinomial)
(nr1, ..., rm)
105PR(4, 2, 1)✗
multinomial(4, 2, 1)
PR(a, b, c, ...) = (a+b+c+...)! / (a!*b!*c!...)
Variaciones
V(7, 7)
5040V(7, 7)✗
P(7, 7)
V(n, n) = P(n, n) = n!
Variaciones
V(7, 2)
42V(7, 7)✗
P(7, 2)
V(n, k) = P(n, k) = C(n, k) k!
Variaciones con repetición
VR(7, 2)
49VR(7, 2)✗
72
VR(n, k) = nk
Factorial
7!
50407!✓
n! = P(n) = P(n, n)
Factorial doble
7!!
1057!!✓
n!! = n(n-2)(n-4)...
Subfactorial
!7
1854!7✓
!n = [n!/e]
Factorial ascendente (Pochhammer)
72
56pochhammer(7, 2)✓
nk = n!/(n-k)!
Factorial descendente
72
42factorialpower(7, 2)✓
nk = (n+k-1)!/(n-1)!

Índice de métodos

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.

  • 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-k n!/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) = n 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) = n 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) y también con
    (nr1, ..., rm)

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

    • permuteR1(list)
      • Permutaciones con repetición o Multinomiales
      • Heap-2: P(n) = n! = n × (n-1)! = n × P(n-1)
      • T(n) =n!-2p +2n+1n! + 2n! - 1 + 2 ∑j=2..nn!
        22j!
      • T'(n) =n!-2p +2n+1n! + n p + 2n! - 1 + 2 ∑j=2..nn!
        22j!
      • Donde p es el valor numérico de las permutaciones con repetición:
        p = PR(r1, ..., rm) =(r1+...+rm)!
        r1!×...×rm!
    • permuteR2(list)
      • Multinomiales mejorado
      • T(n) = ?
      • T'(n)= ?
      • Coste calculado desconocido pues no se pudo definir ni resolver la recurrencia. Cuando los elementos no se repiten, el coste es el mismo que el del algoritmo permuteR1.
    • permuteR3(list)
      • Multinomiales mejorado
      • T(n) = ?
      • T'(n)= ?
      • Coste calculado desconocido pues no se pudo definir ni resolver la recurrencia.

  • 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)
      • Variaciones
      • 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 + T'C1(n, k) + C(n, k) × (1 + T'P1(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)
      • Variaciones
      • V(n, k) = C(n, k) × P(k) = (C(n-1, k-1) + C(n-1, k)) × P(k)
      • T(n, k) = 2 ( ∑ j=0..k C(n, j) ) - 1 - TP1(k) C(n, k)
      • T'(n, k) = 2 ( ∑ j=0..k C(n, j) ) - 1 - T'P1(k) C(n, k)
      • Donde TP1(k) es el coste del algoritmo permute1, tanto con o sin coste de copia.
    • vary3(list, k)
      • Variaciones
      • V(n, k) = n × V(n-1, k-1)

      • El coste con y sin copia es el mismo:

        • k=0 ∨ n<k ⇒ T(n, k) = 1
        • 1 = k ≤ n ⇒ T(n, 1) = n
        • 1 < k ≤ n ⇒
          T(n, k) =n!(1+k2+k-2) + ∑j=n-k+2..n (j2+j+1)n!
          (n-k)!n-k+12j!

      • T'he cost with and without a copy is the same:

        • k=0 ∨ n<k ⇒ T'(n, k) = 1
        • 1 = k ≤ n ⇒ T'(n, 1) = n
        • 1 < k ≤ n ⇒
          T'(n, k) =n!(1+k2+k-2) + ∑j=n-k+2..n (j2+j+1)n!
          (n-k)!n-k+12j!
      • Un segundo valor se obtiene de la fórmula equivalente:
        T(n, k) =n!(k2+k) - (n+3) + 4 ∑j=n-k+1..nn!
        (n-k)!2j!

  • 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)
      • Variaciones con repetición
      • VR(n, k) = nk = n × nk-1 = n × VR(n, k-1)
      • n=1 ⇒ T(n, k) = 2k + 1
        n≠1 ⇒ T(n, k) =2nk+1-n-1
        n-1
      • n=1 ⇒ T'(n, k) = 2k + 1 + k nk
        n≠1 ⇒ T'(n, k) =2nk+1-n-1+ k nk
        n-1

  • Desarreglos D(n)

    Los desarreglos (derangements) de una lista con n elementos distintos son todas las sublistas ordenadas con n elementos distintos que se pueden generar de tal forma que ninguno aparece en su posición original. Una permutación de n elementos tiene uno o más elementos que son puntos fijos si esos elementos se mantienen en su posición original. Desde esta definición un desarreglo es una permutación que no tiene puntos fijos. Se denotan como D(n) o !n denominado subfactorial.

    D(n) = !n = [ n!/e ] = (for n≥1)
    D(n) = n! ∑j=0..n(-1) j = (for n≥0)
    j!

    • derange1(list)
      • Desarreglos
      • D(n) = { ∀ list = ( a1, ..., an ) ∃ P(list) = { p1, ..., pn! } ∧ pi = ( bi,1, ..., bi,j, ..., bi,n ) |
        ∀ j ⇒ bi,j ≠ aj }
      • T(n) = 1 + Tp(n) + (n+2) (n! - !n) + (-1)n
      • T'(n) = 1 + T''p(n) + (n+2) (n! - !n) + (-1)n

      • Otra segunda solución equivalente:

        T(n) = 1 + T'p + (n+2) n! - !n - !(n+1)

        El coste T'p con coste de copia es el del algoritmo permute3(list) basado en el algoritmo de Heap con fórmula:

        T'p(n) = n n! + 2n! - 1 + 2 ∑j=2..nn!
        j!
    • derange2(list)
      • Desarreglos recursivo
      • D(0)=1, D(1)=0, D(n) = (n-1) × (D(n-1) + D(n-2))
      • T(n) =(2n+1)(!n-2)+5+(n-3) !(n+1)+1∑j=0..n-1n!(5+4(-1) jH(n-j))
        424j!
      • T'(n) =(2n+1)(!n-2)+5+(n-3) !(n+1)+1∑j=0..n-1n!(5+4(-1) jH(n-j))
        424j!
      • Esta fórmula es igual para el caso de coste con copia. Incluye H(n) = ∑k=1..n 1/k que es n-ésimo número armónico.

  • Desarreglos parciales D(n, k)

    Los desarreglos parciales de una lista con n elementos distintos son todas las sublistas ordenadas con n elementos distintos que se pueden generar de tal forma que solo k elementos aparecen en su posición original. También se pueden definir como las permutaciones de n elementos con k puntos fijos. Las denotamos como D(n, k), correspondiendo con k=0 a los desarreglos sin puntos fijos que vimos en el tema de Desarreglos.

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

    • derangeP1(list, k)
      • Desarreglos parciales
      • D(n, k) = C(n, k) × D(n-k, 0)
      • m = Max(0, n-k)
        T(n, k) = 1 + n + m + Tc(n, k) + Td(m) + !m (1 + C(n, k) (1+4n+k))
      • m = Max(0, n-k)
        T'(n, k) = 1 + n + m + T'c(n, k) + T'd(m) + !m (1 + C(n, k) (1+4n+k))

      • Donde Tc es el coste de combine2(n, k)

        Tc(n, k) = Max(1, 2 C(n+1, k) - 1 + k C(n, k))

        y Td es el coste de derange1(m)

        Td(m) = 1 + Tp(m) + (m+2) m! - !m - !(m+1)

        y Tp es el coste de permute3(m)

        Tp(m) = m m! + 2 m! - 1 + 2 ∑j=2..mm!
        j!
        (lo resaltado en amarillo es el coste de copia)
    • derangeP2(list, k)
      • Desarreglos parciales 2
      • D(n, k) = n/k D(n-1, k-1)
      • n<k ⇒ T(n, k) = 1
        n≥k ⇒ T(n, k) = !(n-k) C(n, k) (k! + 1) + 1 +
        + 3 ∑j=n-k..nn!- (n+2) +n!(Td(n-k)+n-k-1+!(n-k)k(2n-k+1))
        j!(n-k)!2
      • n<k ⇒ T'(n, k) = 1
        n≥k ⇒ T'(n, k) = !(n-k) C(n, k) (k! + 1) + 1 +
        + 3 ∑j=n-k..nn!- (n+2) +n!(T'd(n-k)+n-k-1+!(n-k)k(2n-k+1))
        j!(n-k)!2

      • Donde Td es el coste de derange1(list) con b=n-k

        Td(b) = 1 + Tp(b) + (b+2) b! - !b - !(b+1)

        y Tp es el coste de permute3(list)

        Tp(b) = b b! + 2b! - 1 + 2 ∑j=2..bb!
        j!
        En caso de copia se agregará lo resaltado en amarillo.
    • derangeP3(list, k)
      • Desarreglos parciales 4
      • D(n, k) = ∑j=k..n D(n-1, j-1)
      • T(n, k) = Max(1, ∑h=0..n-k ∑i=0..k-1 ( C(i+h-1, h) ×
        ( 1 + ∑j=k-i+h..n-i ((n-i) + !(n-k) (n-i) C(n+k-j-2i-1, k-i-1)) )) +
        ∑j=0..n-k C(j+k-1, k-i-1) Td(n-k)))
      • T'(n, k) = Max(1, ∑h=0..n-k ∑i=0..k-1 ( C(i+h-1, h) ×
        ( 1 + ∑j=k-i+h..n-i ((n-i) + !(n-k) (n-i) C(n+k-j-2i-1, k-i-1)) )) +
        ∑j=0..n-k C(j+k-1, k-i-1) T'd(n-k)))

      • Donde Td es el coste de derange1(list) con b=n-k

        Td(b) = 1 + Tp(b) + (b+2) b! - !b - !(b+1)

        y Tp es el coste de permute3(list)

        Tp(b) = b b! + 2b! - 1 + 2 ∑j=2..bb!
        j!
        En caso de copia se agregará lo resaltado en amarillo.