¿Combinatoria ‘N elige R’ en Java Math?

Este dilema se puede solucionar de diferentes maneras, por lo tanto te enseñamos la que en nuestra opinión es la respuesta más completa.

Solución:

La formula

En realidad es muy fácil de calcular. N choose K sin siquiera calcular factoriales.

Sabemos que la fórmula de (N choose K) es:

    N!
 --------
 (N-K)!K!

Por lo tanto, la fórmula para (N choose K+1) es:

       N!                N!                   N!               N!      (N-K)
---------------- = --------------- = -------------------- = -------- x -----
(N-(K+1))!(K+1)!   (N-K-1)! (K+1)!   (N-K)!/(N-K) K!(K+1)   (N-K)!K!   (K+1)

Es decir:

(N choose K+1) = (N choose K) * (N-K)/(K+1)

También sabemos que (N choose 0) es:

 N!
---- = 1
N!0!

Así que esto nos da un punto de partida fácil, y usando la fórmula anterior, podemos encontrar (N choose K) para cualquier K > 0 con K multiplicaciones y K divisiones

---

Triángulo de Pascal fácil

Juntando lo anterior, podemos generar fácilmente el triángulo de Pascal de la siguiente manera:

    for (int n = 0; n < 10; n++) 
        int nCk = 1;
        for (int k = 0; k <= n; k++) 
            System.out.print(nCk + " ");
            nCk = nCk * (n-k) / (k+1);
        
        System.out.println();
    

Esto imprime:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 

---

BigInteger versión

Aplicando la formula de BigInteger es sencillo:

static BigInteger binomial(final int N, final int K) 
    BigInteger ret = BigInteger.ONE;
    for (int k = 0; k < K; k++) 
        ret = ret.multiply(BigInteger.valueOf(N-k))
                 .divide(BigInteger.valueOf(k+1));
    
    return ret;


//...
System.out.println(binomial(133, 71));
// prints "555687036928510235891585199545206017600"

Según Google, 133 elige 71 = 5,55687037 × 10³⁸.

---

Referencias

• Wikipedia/coeficiente binomial
• Wikipedia/triángulo de Pascal
• Wikipedia/combinación

Apache-commons "Math" admite esto en org.apache.commons.math4.util.CombinatoricsUtils

La definición recursiva le brinda una función de elección bastante simple que funcionará bien para valores pequeños. Si planea ejecutar mucho este método, o en valores grandes, valdría la pena memorizarlo, pero por lo demás funciona bien.

public static long choose(long total, long choose) choose == total)
        return 1;
    return choose(total-1,choose-1)+choose(total-1,choose);

Mejorar el tiempo de ejecución de esta función se deja como ejercicio para el lector 🙂

Si guardas algún recelo y capacidad de renovar nuestro sección te recordamos realizar una apostilla y con mucho placer lo estudiaremos.

---

---

Utiliza Nuestro Buscador