Resumen funciones combinatorias que generan listas

Funciones combinatorias que generan listas

Resumen de todas las funciones que generan listas en la aplicación Combine Tools Para cada función se incluyen uno o más algoritmos, principalmente usando recursivos. Tambié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.

  • 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.

    Valor numérico:
    C(n, k) =n!=
    k!*(n-k)!

    • combine1(list, k)
      • Combinaciones sin repetición
      • Base matemática
        C(n, k) = C(n-1, k-1) + C(n-1, k)
      • Coste
        T(n, k) = 2 ( ∑j=0..k C(n, j) ) - 1
      • Coste con copia
        T'(n, k) = 2 ( ∑j=0..k C(n, j) ) - 1 + k C(n, k)
    • combine2(list, k)
      • Combinaciones sin repetición: algoritmo mejorado
      • Base matemática
        C(n, k) = ∑j=k..n C(j-1, k-1)
      • Coste
        n<k ⇒ T(n, k) = k+1
        n≥k ⇒ T(n, k) = 2 C(n+1, k) - 1 + k
      • Coste con copia
        n<k ⇒ T'(n, k) = k+1
        n≥k ⇒ T'(n, k) = 2 C(n+1, k) - 1 + k + k C(n, k)

  • Combinaciones complementarias C(n, 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. 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 Si,k designa uno de esos subconjuntos de combinaciones con 1 ≤ i ≤ C(n, k), entonces A - Si,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.

    Valor numérico:
    C(n, n-k) =n!=
    (n-k)!*k!

    • combineComplement1(list, k)
      • Combinaciones complementarias
      • Base matemática
        C(n, k) = C(n, n-k) = ∑j=k..n C(j-1, k-1)
      • Coste
        n<k ⇒ T(n, k) = k+1
        n≥k ⇒ T(n, k) = 2 C(n+1, k) - 1 + n k C(n, k) + k
      • Coste con copia
        n<k ⇒ T'(n, k) = k+1
        n≥k ⇒ T'(n, k) = 2 C(n+1, k) - 1 + n k C(n, k) + k + k C(n, k)
    • combineComplement2(list, k)
      • Combinaciones complementarias
      • Base matemática
        C(n, k) = C(n, n-k) = ∑j=k..n C(j-1, k-1)
      • Coste
        k=0 ∨ n<k ⇒ t(n, k) = 1
        t(n, k) = n + C(n, k) - 1 + t(n-1, k-1) + t(n-1, k)
        T(n, k) = t(n, k) + n + k
      • Coste con copia
        k=0 ∨ n<k ⇒ t'(n, k) = 1
        t'(n, k) = n + C(n, k) - 1 + t'(n-1, k-1) + t'(n-1, k)
        T'(n, k) = t'(n, k) + n + k + n C(n, k)
      • Notas
        Como alternativa tenemos también dos recurrencias, la primera:
        b = n0 - k0
        k=0 ∨ n<k ⇒ t'(n, k, b) = 1,
        t'(n, k, b) = k + b + t'(n-1, k-1, b) + t'(n-1, k, b)
        T'(n, k, b) = t'(n, k, b) + n + k + n C(n, k)
        Y la segunda que es una aplicación directa del algoritmo
        b = n0 - k0
        k=0 ⇒ t'(n, k, b) = 1,
        t'(n, k, b) = ∑j=k..n k + b + t'(j-1, k-1, b)
        T'(n, k, b) = t'(n, k, b) + n + k + n C(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.

    Valor numérico:
    CR(n, k) = C(n+k-1, k) =(n+k-1)!=
    k!*(n-1)!

    • combineR1(list, k)
      • Combinaciones con repetición
      • Base matemática
        CR(n, k) = CR(n, k-1) + CR(n-1, k)
      • Coste
        T(n, k) = 2 C(n+k, k) - 1
      • Coste con copia
        T'(n, k) = 2 C(n+k, k) - 1 + k C(n+k-1, k)
    • combineR2(list, k)
      • Combinaciones con repetición (2)
      • Base matemática
        CR(n, k) = ∑j=0..n-1 CR(j+1, k-1)
      • Coste
        T(n, k) = 2 C(n+k, k) - 1 + k
      • Coste con copia
        T'(n, k) = 2 C(n+k, k) - 1 + k + k C(n+k-1, k)

  • 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.

    Valor numérico:
    K(n, k) = ∑j=0..n-k n!/j! =

    • kTuples1(list)
      • K-Tuplas (1)
      • Base matemática
        K(n, k) = ∑j=k..n C(n, j) P(j)
      • Coste
        T(n, k) = 1 + ∑j=k..n ( 1 + TC2(n, j) + C(n, j) ( 1 + j + TP2(j) ) )
      • Coste con copia
        T'(n, k) = 1 + ∑j=k..n ( 1 + T'C2(n, j) + C(n, j) ( 1 + j + T'P2(j) ) )
      • Notas
        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.

    Valor numérico:
    P(n) = n! =

    • permute1(list)
      • Permutar un Array con un recursivo
      • Combinatoria: Permutaciones
      • Base matemática
        P(n) = n! = n × (n-1)! = n × P(n-1)
      • Coste
        T(n) = Max ( 1, n! (n2+n-5+ ∑j=3..nj2+j+1) )
        2j!
      • Coste con copia
        T'(n) = Max ( 1, n! (n2+n-5+ ∑j=3..nj2+j+1) )
        2j!
      • Notas
        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
      • Base matemática
        Heap: P(n) = n! = n × (n-1)! = n × P(n-1)
      • Coste
        T(n) = 1 + 2 ∑j=2..nn!
        (n-j+1)!
      • Coste con copia
        T'(n) = n n! + 1 + 2 ∑j=2..nn!
        (n-j+1)!
      • Notas
        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
      • Base matemática
        Heap-2: P(n) = n! = n × (n-1)! = n × P(n-1)
      • Coste
        T(n) = 1 + 2 ∑j=2..nn!
        (n-j+1)!
      • Coste con copia
        T'(n) = n n! + 1 + 2 ∑j=2..nn!
        (n-j+1)!
      • Notas
        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)

    Valor numérico:
    PR( r1, ..., rm ) =( r1 + ... + rm )!=
    r1! × ... × rm!

    • permuteR1(list)
      • Permutaciones con repetición o Multinomiales
      • Base matemática
        Heap-2: P(n) = n! = n × (n-1)! = n × P(n-1)
      • Coste
        T(n) =n!-2p +2n+1n! + 2n! - 1 + 2 ∑j=2..nn!
        22j!
      • Coste con copia
        T'(n) =n!-2p +2n+1n! + n p + 2n! - 1 + 2 ∑j=2..nn!
        22j!
      • Notas
        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
      • Coste
        T(n) = ?
      • Coste con copia
        T'(n)= ?
      • Notas
        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
      • Coste
        T(n) = ?
      • Coste con copia
        T'(n)= ?
      • Notas
        Unknown calculated cost since the recurrence could not be defined or resolved.

  • 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.

    Valor numérico:
    V(n, k) = C(n, k) P(k, k) = C(n, k) k! =n!=
    (n-k)!

    • vary1(list, k)
      • Variaciones
      • Base matemática
        V(n, k) = C(n, k) × P(k)
      • Coste
        T(n, k) = 1 + TC1(n, k) + C(n, k) × (1 + TP1(k))
      • Coste con copia
        T'(n, k) = 1 + T'C1(n, k) + C(n, k) × (1 + T'P1(k))
      • Notas
        Donde T'C1(n, k) es el coste del algoritmo combine1 y T'P1(k) es el del algoritmo permute1, iguales para con o sin coste de copia.
    • vary2(list, k)
      • Variaciones
      • Base matemática
        V(n, k) = C(n, k) × P(k) = (C(n-1, k-1) + C(n-1, k)) × P(k)
      • Coste
        T(n, k) = 2 ( ∑ j=0..k C(n, j) ) - 1 - TP1(k) C(n, k)
      • Coste con copia
        T'(n, k) = 2 ( ∑ j=0..k C(n, j) ) - 1 - T'P1(k) C(n, k)
      • Notas
        Donde T'P1(k) es el coste del algoritmo permute1, tanto con o sin coste de copia.
    • vary3(list, k)
      • Variaciones
      • Base matemática
        V(n, k) = n × V(n-1, k-1)
      • Coste
        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!
      • Coste con copia
        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!
      • Notas
        El coste con y sin copia es el mismo. 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).

    Valor numérico:
    VR(n, k) =nk =

    • varyR1(list, k)
      • Variaciones con repetición
      • Base matemática
        VR(n, k) = nk = n × nk-1 = n × VR(n, k-1)
      • Coste
        n=1 ⇒ T(n, k) = 3k + 1
        n≠1 ⇒ T(n, k) =2nk+1-n-1+ k
        n-1
      • Coste con copia
        n=1 ⇒ T'(n, k) = 3k + 1 + k nk
        n≠1 ⇒ T'(n, k) =2nk+1-n-1+ k nk + k
        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.

    Valor numérico:
    D(n) = !n = [ n!/e ] = (for n≥1)
    D(n) = n! ∑j=0..n(-1) j = (for n≥0)
    j!

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

        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
      • Base matemática
        D(0)=1, D(1)=0, D(n) = (n-1) × (D(n-1) + D(n-2))
      • Coste
        T(n) =(2n+1)(!n-2)+5+(n-3) !(n+1)+1∑j=0..n-1n!(5+4(-1) jH(n-j))
        424j!
      • Coste con copia
        T'(n) =(2n+1)(!n-2)+5+(n-3) !(n+1)+1∑j=0..n-1n!(5+4(-1) jH(n-j))
        424j!
      • Notas
        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.

    Valor numérico:
    D(n, k) = C(n, k) × !(n-k) =

    • derangeP1(list, k)
      • Desarreglos parciales
      • Base matemática
        D(n, k) = C(n, k) × D(n-k, 0)
      • Coste
        m = Max(0, n-k)
        T(n, k) = 1 + n + m + Tc(n, k) + Td(m) + !m (1 + C(n, k) (1+4n+k))
      • Coste con copia
        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))
      • Notas

        Donde T'c es el coste de combine2(n, k)

        T'c(n, k) = Max(1, 2 C(n+1, k) - 1 + k C(n, k))

        y T'd es el coste de derange1(m)

        T'd(m) = 1 + Tp(m) + (m+2) m! - !m - !(m+1)

        y T'p es el coste de permute3(m)

        T''p(m) = m m! + 2 m! - 1 + 2 ∑j=2..mm!
        j!
    • derangeP2(list, k)
      • Desarreglos parciales 2
      • Base matemática
        D(n, k) = n/k D(n-1, k-1)
      • Coste
        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
      • Coste con copia
        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
      • Notas

        Donde T'd es el coste de derange1(list) con b=n-k

        T'd(b) = 1 + Tp(b) + (b+2) b! - !b - !(b+1)

        y T'p es el coste de permute3(list)

        T'p(b) = b b! + 2b! - 1 + 2 ∑j=2..bb!
        j!
    • derangeP3(list, k)
      • Desarreglos parciales 4
      • Base matemática
        D(n, k) = ∑j=k..n D(n-1, j-1)
      • Coste
        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))
      • Coste con copia
        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))
      • Notas

        Donde T'd es el coste de derange1(list) con b=n-k

        T'd(b) = 1 + Tp(b) + (b+2) b! - !b - !(b+1)

        y T'p es el coste de permute3(list)

        T'p(b) = b b! + 2b! - 1 + 2 ∑j=2..bb!
        j!

  • Número de Bell: particiones y rimas B(n)

    El número de Bell Bn, que denotaremos como B(n), representa el total de particiones de un conjunto con n elementos. Una partición de un conjunto son los agrupamientos de sus elementos en subconjuntos no vacíos, de tal forma que cada elemento está incluido en un único subconjunto, así que los subconjuntos son disjuntos. Por ejemplo, si el conjunto de partida es A = {a, b, c}, una partición es {{a, b}, {c}}, donde se evidencia que la unión de estos subconjuntos {a, b} ⋃ {c} = A es el conjunto de partida. Y que la intersección {a, b} ⋂ {c} = ∅ es vacía, que es lo mismo que decir que los subconjuntos son disjuntos.

    Las particiones también cuentan el número de esquemas de rimas de un poema. Entonces podemos generar B(n) particiones y por tanto rimas distintas. Si el conjunto de partida son n líneas de poemas numeradas 1..n, podemos generar B(n) posibles formas de disponer las rimas en esas líneas.
    Por ejemplo, con n=3 disponemos del conjunto de partida de líneas numeradas {1, 2, 3}, generándose las particiones 123, 12.3, 13.2, 1.23, 1.2.3 expresadas de forma compacta. Cada dígito representa la línea donde hemos de incluir una rima entre [A, B, C], que se van seleccionando en orden. Así una partición como 12.3 se traduce como AAB indicando que las 2 primeras líneas riman, pues están en el mismo subconjunto. Y la tercera no rima con ninguna al ser única en su subconjunto.

    Valor numérico:
    B(0) = 1,
    B(n) = ∑j=0..n-1 C(n-1, j) B(j) =

    • partition1(list)
      • Particiones
      • Base matemática
        B(n) = ∑j=0..n-1 C(n-1, j) B(j)
      • Coste
        n≤2 ⇒ T(n) = 1,
        T(n) = (n+17) 2n-2 + n2 - n - 4 + B(n) + ∑j=0..n-1 C(n-1, j) T(j)
      • Coste con copia
        n≤2 ⇒ T'(n) = 1,
        T'(n) = (3n+15) 2n-2 + n2 - n - 4 + B(n) + ∑j=0..n-1 C(n-1, j) T'(j)
      • Notas
        Donde B(n) son los números de Bell, para lo cual no hay una fórmula cerrada, calculándose con la recurrencia siguiente
        B(0) = 1,
        B(n) = ∑j=0..n-1 C(n-1, j) B(j)
    • partition2(list)
      • Primer algoritmo mejorado para generar particiones
      • Base matemática
        B(n) = ∑j=0..n-1 C(n-1, j) B(j)
      • Coste
        n≤2 ⇒ T(n) = 1,
        T(n) = (n2-n+10) 2n-2 + 1/2 (n2+n-4) + B(n) + ∑j=0..n-1 C(n-1, j) T(j)
      • Coste con copia
        n≤2 ⇒ T'(n) = 1,
        T'(n) = (n2+9) 2n-2 + 1/2 (n2+n-4) + B(n) + ∑j=0..n-1 C(n-1, j) T'(j)
      • Notas
        Donde B(n) son los números de Bell, para lo cual no hay una fórmula cerrada, calculándose con la recurrencia siguiente
        B(0) = 1,
        B(n) = ∑j=0..n-1 C(n-1, j) B(j)
    • partition3(list)
      • Segundo algoritmo mejorado para generar particiones
      • Base matemática
        B(n) = ∑j=0..n-1 C(n-1, j) B(j)
      • Coste
        n≤2 ⇒ T(n) = 1,
        T(n) = (n+1) 2n-2 + 2n + B(n) + ∑j=0..n-1 (Tc(n-1, j) + C(n-1, j) T(j))
      • Coste con copia
        n≤2 ⇒ T'(n) = 1,
        T'(n) = (n+1) 2n-2 + 2n + B(n) + ∑j=0..n-1 (T'c(n-1, j) + C(n-1, j) T'(j))
      • Notas
        Donde B(n) son los números de Bell, para lo cual no hay una fórmula cerrada, calculándose con la recurrencia siguiente
        B(0) = 1,
        B(n) = ∑j=0..n-1 C(n-1, j) B(j)
        Y T'c(n, k) son las combinaciones complementarias del algoritmo combineComplement2(n, k) para lo que no he encontrado una fórmula cerrada:
        k=0 ∨ n<k ⇒ t'(n, k) = 1,
        t'(n, k) = n + C(n, k) - 1 + t'(n-1, k-1) + t'(n-1, k),
        T'(n, k) = t'(n, k) + n + k + n C(n, k)
    • partition4(list)
      • Algoritmo para generar particiones usando números de Stirling de segunda clase
      • Base matemática
        n=k ⇒ S2(n, k) = 1,
        n=0 ∨ k=0 ∨ n<k ⇒ S2(n, k) = 0,
        S2(n, k) = S2(n-1, k-1) + k × S2(n-1, k)
      • Coste
        T(n) = B(n) + ∑i=1..n ∑j=1..i S2(i, j)
      • Coste con copia
        T'(n) = n B(n) + B(n) + ∑i=1..n ∑j=1..i S2(i, j)
      • Notas
        Otra segunda solución equivalente:
        T'(n) = n B(n) + B(n) + ∑i=0..n C(n, i+1) B(i)

        Donde
        B(n) = ∑j=0..n-1 C(n-1, j) B(j)
        son los números de Bell y
        S2(n, k) =1∑j=0..k (-1)k-j C(k, j) jn
        k!
        es la fórmula cerrada para los números de Stirling de segunda clase.
    • partition5(list)
      • Algoritmo para generar particiones usando particiones parciales
      • Base matemática
        B(n) = ∑j=0..n S2(n, j)
        Donde S2(n, k) es el número de Stirling de segunda clase con recurrencia:
        n=k ⇒ S2(n, k) = 1,
        n=0 ∨ k=0 ∨ n<k ⇒ S2(n, k) = 0,
        S2(n, k) = S2(n-1, k-1) + k × S2(n-1, k)
      • Coste
        T(n) = 1 + n + B(n) + ∑k=1..n Tk(n, k)
      • Coste con copia
        T'(n) = 1 + n + B(n) + ∑k=1..n T'k(n, k)
      • Notas
        Donde T'k es el coste con copia de las particiones parciales del algoritmo kPartition1(list, k) con fórmula recurrente:
        n<k ∨ k=0 ⇒ T'(n, k) = 1
        n=k ∨ k=1 ⇒ T'(n, k) = n
        T'(n, k) = n + T'(n-1, k-1) + T'(n-1, k) + S2(n-1, k-1) (1+n+k) + S2(n-1, k) (1+(k(1+n+k))
        Siendo B(n) el número de Bell con fórmula:
        B(0) = 1,
        B(n) = ∑j=0..n-1 C(n-1, j) B(j)
    • partition6(list)
      • Algoritmo para generar particiones usando particiones parciales
      • Base matemática
        n=k ⇒ S2(n, k) = 1,
        n=0 ∨ k=0 ∨ n<k ⇒ S2(n, k) = 0,
        k=1 ⇒ S2(n, k) = 1,
        S2(n, k) = ∑j=0..n-1 S2(j, k-1) C(n-1, j)
      • Coste
        T(n) = 1 + n + B(n) + ∑k=1..n Tk(n, k)
      • Coste con copia
        T'(n) = 1 + n + B(n) + ∑k=1..n T'k(n, k)
      • Notas
        Donde T'k es el coste con copia de las particiones parciales del algoritmo kPartition2(list, k) con fórmula recurrente:
        n=k ⇒ T'(n, k) = n,
        n=0 ∨ k=0 ∨ n< k ⇒ T'(n, k) = 1,
        k=1 ⇒ T'(n, k) = n,
        T'(n, k) = (n+1) 2n-2 + 2n + S2(n, k) + ∑j=0..n-1 (Tcc(n-1, j) + C(n-1, j) T'(j, k-1))
        Siendo B(n) el número de Bell con fórmula:
        B(0) = 1,
        B(n) = ∑j=0..n-1 C(n-1, j) B(j)
    • rhymes1(list)
      • Primer algoritmo para implementar rimas
      • Base matemática
        B(0) = 1, B(n) = ∑j=0..n S2(n, j)
        n=k ⇒ S2(n, k) = 1,
        n=0 ∨ k=0 ∨ n<k ⇒ S2(n, k) = 0,
        S2(n, k) = S2(n-1, k-1) + k × S2(n-1, k)
      • Coste
        T(n) = n + Tp(n) + 2 B(n, n-1) + (n+2) B(n) - B(n+1)
      • Notas
        Donde Tp(n) es el coste del algoritmo partition4(list):
        Tp(n) = B(n) + ∑i=1..n ∑j=1..i S2(i, j)
        Siendo B(n) el número de Bell y B(n, k) son los valores del Triángulo de Bell que se calcula con la recurrencia:
        B(0, 0) = 1,
        B(n, 0) = B(n-1, n-1),
        B(n, k) = B(n, k-1) + B(n-1, k-1)
    • rhymes2(list)
      • Segundo algoritmo para implementar rimas
      • Base matemática
        B(0) = 1, B(n) = ∑j=0..n S2(n, j)
        n=k ⇒ S2(n, k) = 1,
        n=0 ∨ k=0 ∨ n<k ⇒ S2(n, k) = 0,
        S2(n, k) = S2(n-1, k-1) + k × S2(n-1, k)
      • Coste
        T(n) = 2 B(n, n-1) + (n+2) B(n) - B(n+1) + ∑i=0..n C(n+1, i+1) B(i)
      • Coste con copia
        T'(n) = 2 B(n, n-1) + (n+2) B(n) - B(n+1) + ∑i=0..n C(n+1, i+1) B(i)
      • Notas
        El coste es el mismo con y sin copia. Siendo B(n) el número de Bell y B(n, k) son los valores del Triángulo de Bell que se calcula con la recurrencia:
        B(0, 0) = 1,
        B(n, 0) = B(n-1, n-1),
        B(n, k) = B(n, k-1) + B(n-1, k-1)

  • Números de Stirling de primera clase: Permutaciones cíclicas S(n, k)

    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. Un ciclo se presenta con una permutación entre paréntesis. Los ciclos son como las particiones 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 una permutación cíclica como (a)(b)(cd) es lo mismo que (b)(cd)(a) y cualquiera de las otras posibles permutaciones de los ciclos.
    Con el conjunto de elementos {a, b, c} tenemos 2 permutaciones cíclicas de longitud 1 ciclo (permutaciones circulares): (abc), (acb). Las permutaciones (abc) = (cab) = (bca) se refieren a la misma permutación cíclica, acostumbrándose a usar la primera abc como representante de ese conjunto de ciclos por estar mejor ordenada. Y la otra es (acb) representante de (bac) = (cba) = (acb), aunque pudiera usarse cualquiera de las tres como representante del conjunto cíclico. La forma canónica es aquella que ordena los ciclos por su primer elemento, y, dentro de cada ciclo, selecciona aquella disposición cuyo primer elemento sea el menor en orden. Por ejemplo (cbd)(a) se canoniza como (a)(bdc).

    Valor numérico:
    n=k ⇒ S(n, k) = 1,
    n=0 ∨ k=0 ∨ n<k ⇒ S(n, k) = 0,
    S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1) =

    • permuteCycles1(list)
      • Primer algoritmo para generar permutaciones cíclicas
      • Base matemática
        n=k ⇒ S(n, k) = 1,
        n=0 ∨ k=0 ∨ n<k ⇒ S(n, k) = 0,
        S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1)
      • Coste
        n=k ⇒ T(n, k) = n
        n=0 ∨ k=0 ∨ n<k ⇒ T(n, k) = 1
        T(n, k) ≤ n + T(n-1, k-1) + T(n-1, k) + S(n-1, k-1) k + S(n-1, k) (2n2-2n+k+1)
      • Coste con copia
        n=k ⇒ T'(n, k) = n
        n=0 ∨ k=0 ∨ n<k ⇒ T'(n, k) = 1
        T'(n, k) ≤ n + T'(n-1, k-1) + T'(n-1, k) + S(n-1, k-1) k + S(n-1, k) (2n2-2n+k+1)
      • Notas
        El coste anterior es una cota superior pues no pude determinarlo con exactitud. La recurrencia S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1) calcula los números de Stirling de primera clase sin signo. El coste con y sin copia es el mismo.
    • permuteCycles2(list)
      • Segundo algoritmo para generar permutaciones cíclicas
      • Base matemática
        n=k ⇒ S(n, k) = 1,
        k=0 ∨ n<k ⇒ S(n, k) = 0,
        k=1 ∧ n>k ⇒ S(n, k) = (n-1)!,
        k>1 ∧ n>k ⇒ S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1)
      • Coste
        n=k ⇒ T(n, k) = n,
        n=0 ∨ k=0 ∨ n<k ⇒ T(n, k) = 1,
        k=1 ⇒ T(n, k) = n(1+(n-1)!) + Tp(n-1),
        T(n, k) ≤ n + T(n-1, k-1) + T(n-1, k) + S(n-1, k-1) k + S(n-1, k) (2n2-2n+k+1)
      • Coste con copia
        n=k ⇒ 'T(n, k) = n,
        n=0 ∨ k=0 ∨ n<k ⇒ T'(n, k) = 1,
        k=1 ⇒ T'(n, k) = n(1+(n-1)!) + T'p(n-1),
        T'(n, k) ≤ n + T(n-1, k-1) + T(n-1, k) + S(n-1, k-1) k + S(n-1, k) (2n2-2n+k+1)
      • Notas
        El coste anterior es una cota superior pues no pude determinarlo con exactitud. En un caso base tenemos Tp como el coste del algoritmo permute3(list):
        Tp(n) = n n! + 1 + 2 ∑j=2..nn!
        (n-j+1)!
        En caso de copia se agrega lo resaltado en amarillo. La recurrencia S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1) calcula los números de Stirling de primera clase sin signo.
    • permuteCycles3(list)
      • Tercer algoritmo para generar permutaciones cíclicas
      • Base matemática
        n=k ⇒ S(n, k) = 1,
        n=0 ∨ k=0 ∨ n<k ⇒ S(n, k) = 0,
        S(n, k) = ∑j=k-1..n-1 S(n-1, j) C(j, k-1)
      • Coste
        n=k ⇒ T(n, k) = n,
        n=0 ∨ k=0 ∨ n<k ⇒ T(n, k) = 1,
        T(n, k) ≤ 1 + (n-1) + ∑j=k-1..n-1 ( 1 + T(n-1, j) + j + Tc(j, k-1) +
        S(n-1, j) (1 + C(j, k-1) (1 + q)))
      • Coste con copia
        n=k ⇒ T'(n, k) = n,
        n=0 ∨ k=0 ∨ n<k ⇒ T'(n, k) = 1,
        T'(n, k) ≤ 1 + (n-1) + ∑j=k-1..n-1 ( 1 + T'(n-1, j) + j + Tc(j, k-1) +
        S(n-1, j) (1 + C(j, k-1) (1 + q)))
      • Notas

        Supone una cota superior, 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 Tc(j, k-1) es el coste del algoritmo combine2(list, k) calculado con lo siguiente, 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)

        n<k ⇒ T(n, k) = k+1
        n≥k ⇒ T(n, k) = 2 C(n+1, k) - 1 + k + k C(n, k)

        Además tenemos la variable q como estimación)

        q = {j2 + rj>k
        j2+n+kj=k
        n+kj<k

        donde a su vez r es otra estimación, siendo cero con n0, k0 los valores iniciales en la ejecución del algoritmo y en otro caso se estima en (n-k)2

        r = {0n=n0 ∧ k=k0
        (n-k)2otherwise

  • Números de Stirling de segunda clase: Particiones parciales S2(n, k)

    Un número de Stirling de segunda clase es el número de formas de particionar un conjunto de n elementos en k subconjuntos no vacíos, denotándose como S2(n, k) o {nk}. El total de particiones es el número de Bell relacionándose con B(n) = ∑j=0..n S2(n, j).
    Como S2(n, k) son las particiones con k subconjuntos las podemos denominar particiones parciales de longitud k.

    Valor numérico:
    Recurrencia:
    n=k ⇒ S2(n, k) = 1,
    n=0 ∨ k=0 ∨ n<k ⇒ S2(n, k) = 0,
    S2(n, k) = S2(n-1, k-1) + k × S2(n-1, k) =
    Fórmula cerrada:
    S2(n, k) =1∑j=0..k (-1)k-j C(k, j) jn =
    k!

    • kPartition1(list)
      • Particiones y números de Stirling de segunda clase
      • Base matemática
        S2(n, k) = S2(n-1, k-1) + k × S2(n-1, k)
      • Coste
        n<k ∨ k=0 ⇒ T(n, k) = 1
        n=k ∨ k=1 ⇒ T(n, k) = n
        T(n, k) = n + T(n-1, k-1) + T(n-1, k) + S2(n, k) + S2(n-1, k)
      • Coste con copia
        n<k ∨ k=0 ⇒ T'(n, k) = 1
        n=k ∨ k=1 ⇒ T'(n, k) = n
        T'(n, k) = n + T'(n-1, k-1) + T'(n-1, k) +
        S2(n-1, k-1) (1+n+k) + S2(n-1, k) (1 + k (1+n+k))
      • Notas
        Donde S2(n, k) es el número de Stirling de segunda clase:
        S2(n, k) =1∑j=0..k (-1)k-j C(k, j) jn =
        k!
    • kPartition2(list)
      • Particiones y números de Stirling de segunda clase
      • Base matemática
        n=k ⇒ S2(n, k) = 1,
        n=0 ∨ k=0 ∨ n<k ⇒ S2(n, k) = 0,
        k=1 ⇒ S2(n, k) = 1,
        S2(n, k) = ∑j=0..n-1 S2(j, k-1) C(n-1, j)
      • Coste
        n=k ⇒ T(n, k) = n,
        n=0 ∨ k=0 ∨ n< k ⇒ T(n, k) = 1,
        k=1 ⇒ T(n, k) = n,
        T(n, k) = (n+1) 2n-2 + 2n + S2(n, k) + ∑j=0..n-1 (Tcc(n-1, j) + C(n-1, j) T(j, k-1))
      • Coste con copia
        n=k ⇒ T'(n, k) = n,
        n=0 ∨ k=0 ∨ n< k ⇒ T'(n, k) = 1,
        k=1 ⇒ T'(n, k) = n,
        T'(n, k) = (n+1) 2n-2 + 2n + S2(n, k) + ∑j=0..n-1 (T'cc(n-1, j) + C(n-1, j) T'(j, k-1))
      • Notas

  • Particiones con semi bloques sB(n, k)

    Las particiones con semi bloques parciales (o semi Bell) que denominaremos sB(n, k) son las particiones de un conjunto con n elementos tal que ninguno de los subconjuntos (o bloques) son de longitud igual a k. Por ejemplo, para el conjunto con n elementos {a, b, c} tenemos con k=1 la única partición abc expresada de forma compacta, donde ningún subconjunto o bloque tienen longitud unitaria; con k=2 tenemos abc, a.b.c; con k=3 tenemos ab.c, ac.b, a.bc, a.b.c; mientras que con k=0 o k>3 tenemos todas las particiones posibles abc, ab.c, ac.b, a.bc, a.b.c

    Valor numérico:
    n=0 ⇒ sB(n, k) = 1,
    sB(n, k) = ∑j=1..n (1 - δj,k) C(n-1, j-1) sB(n-j, k) =

    • semiPartition1(list, k)
      • Particiones con semi bloques
      • Base matemática
        n=0 ⇒ sB(0, k) = 1,
        sB(n, k) = ∑j=1..n (1 - δj,k) C(n-1, j-1) sB(n-j, k)
      • Coste
        T(0, k) = 1,
        T(n, k) = 2n + (n+1) 2n-2 - C(n-1, k-1) k +
        ∑j=1..n (1 - δj,k) ( Tcc(n-1, j-1) + C(n-1, j-1) ( sB(n-j, k) + T(n-j, k) ) )
      • Coste con copia
        T'(0, k) = 1,
        T'(n, k) = 2n + (n+1) 2n-2 - C(n-1, k-1) k +
        ∑j=1..n (1 - δj,k) (Tcc(n-1, j-1) + C(n-1, j-1) ( sB(n-j, k) + T'(n-j, k) ) )
      • Notas
        Donde sB(n, k) son las particiones con semi bloques parciales (o semi Bell), para lo cual no hay una fórmula cerrada, calculándose con la recurrencia siguiente
        sB(0, k) = 1, sB(n, k) = ∑j=1..n (1 - δj,k) C(n-1, j-1) sB(n-j, k)
        Y T'cc(n, k) son las combinaciones complementarias del algoritmo combineComplement2(n, k) para lo que no he encontrado una fórmula cerrada:
        k=0 ∨ n<k ⇒ t'(n, k) = 1
        t'(n, k) = n + C(n, k) - 1 + t'(n-1, k-1) + t'(n-1, k)
        T'(n, k) = t'(n, k) + n + k + n C(n, k)

  • Particiones con bloques parciales pB(n, k)

    Las particiones con bloques parciales (o Bell parcial) que denominaremos pB(n, k) son las particiones de un conjunto con n elementos tal que alguno de los subconjuntos (o bloques) son de longitud igual a k. Por ejemplo, para el conjunto con n elementos {a, b, c} tenemos con k=1 las particiones ab.c, ac.b, a.bc, a.b.c expresadas de forma compacta, donde todos los subconjuntos o bloques tienen al menos uno de longitud unitaria; con k=2 tenemos ab.c, ac.b, a.bc; con k=3 tenemos abc; mientras que con k=0 tenemos todas las particiones posibles abc, ab.c, ac.b, a.bc, a.b.c
    Se calculan usando sB(n, k) que son las particiones con semi bloques, de tal forma que pB(n, k) = sB(n, 0) - sB(n, k), observando que sB(n, 0) = B(n), lo que significa que es la diferencia entre el total de particiones y todas aquellas que no tienen bloques de longitud k

    Valor numérico:
    k=0 ⇒ pB(n, k) = sB(n, 0) = B(n, 0) = ,
    pB(n, k) = sB(n, 0) - sB(n, k) =
    n=0 ⇒ sB(n, k) = 1,
    sB(n, k) = ∑j=1..n (1 - δj,k) C(n-1, j-1) sB(n-j, k) =

    • partialPartition1(list, k)
      • Particiones con bloques parciales
      • Base matemática
        pB(n, k) = B(n) - sB(n, k)
      • Coste
        T(n, k) ≤ 1 + Tp(n) + B(n) + ∑j=0..n j S2(n, j)
      • Coste con copia
        T'(n, k) ≤ 1 + T'p(n) + B(n) + ∑j=0..n j S2(n, j)
      • Notas
        Fórmula del coste como cota superior, que sería igual si omitimos la sentencia break en el bucle interior del algoritmo, sentencia que reduce el coste, pero no he podido determinarlo incluyendo break.
        El coste Tp(n) es el del algoritmo partition4(list):
        Tp(n) = n B(n) + B(n) + ∑i=0..n C(n, i+1) B(i)
        agregándose lo resaltado en caso de copia.

  • Rimas coincidentes rB(n)

    Las rimas coincidentes se refiere a evitar aquellos poemas donde no haya ningún verso que no rime con otros. Esto equivale a evitar particiones con bloques unitarios.
    Hay B(n) particiones para un conjunto con n elementos. Si quitamos las particiones que contengan subconjuntos o bloques unitarios, denominaremos rB(n) al resto de las particiones sin bloques unitarios. Se calcula con rB(n) = pB(n-1, 1) particiones usando las particiones con bloques parciales pB(n, k).

    Valor numérico:
    rB(n) = pB(n-1, 1) =

    • matchingRhymes(list)
      • Particiones con rimas coincidentes
      • Base matemática
        B(0) = 1, B(n) = ∑j=0..n S2(n, j)
        n=k ⇒ S2(n, k) = 1,
        n=0 ∨ k=0 ∨ n<k ⇒ S2(n, k) = 0,
        S2(n, k) = S2(n-1, k-1) + k × S2(n-1, k)
      • Coste
        T(n) ≤ B(n) + 4/7 × ( n B(n) + ∑j=0..n j S2(n, j) ) + ∑i=0..n C(n, i+1) B(i)
      • Coste con copia
        T'(n) ≤ B(n) + 4/7 × ( n B(n) + ∑j=0..n j S2(n, j) ) + ∑i=0..n C(n, i+1) B(i)
      • Notas
        El coste que pude estimar es una cota superior condicionada por la existencia de la sentencia break, usando la fracción 4/7 válida al menos para valores n = 0..12