Combinatoire "N choisit R" en java math ?

Question

Existe-t-il une méthode intégrée dans une bibliothèque java qui permet de calculer 'N choisir R' pour tout N, R ?

Answer 1

La formule

C'est en fait très facile à calculer N choose K sans même calculer les factorielles.

Nous savons que la formule pour (N choose K) est :

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

Par conséquent, la formule pour (N choose K+1) est :

       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)

C'est-à-dire :

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

Nous savons également que (N choose 0) est :

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

Cela nous donne donc un point de départ facile, et en utilisant la formule ci-dessus, nous pouvons trouver (N choose K) pour tout K > 0 con K les multiplications et K divisions.

---

Triangle de Pascal facile

En combinant les éléments ci-dessus, nous pouvons facilement générer le triangle de Pascal comme suit :

    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();
    }

Cette empreinte :

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 version

En appliquant la formule pour BigInteger est simple :

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"

Selon Google, 133 choisir 71 = 5,55687037 × 10 38 .

---

Références

• Wikipedia/Coefficient binomial
• Wikipédia/Triangle de Pascal
• Wikipedia/Combinaison

Answer 2

Le module "Math" d'apache-commons prend en charge cette fonction en org.apache.commons.math4.util.CombinatoricsUtils

Answer 3

El définition récursive vous donne une fonction de choix assez simple qui fonctionnera bien pour les petites valeurs. Si vous prévoyez d'utiliser cette méthode souvent, ou sur de grandes valeurs, il serait utile de la mémoriser, mais sinon, elle fonctionne très bien.

public static long choose(long total, long choose){
    if(total < choose)
        return 0;
    if(choose == 0 || choose == total)
        return 1;
    return choose(total-1,choose-1)+choose(total-1,choose);
}

L'amélioration de la durée d'exécution de cette fonction est laissée à l'appréciation de la Commission. exercice pour le lecteur :)

Answer 4

J'essaie simplement de calculer le nombre de combinaisons de 2 cartes avec différentes tailles de jeux...

Pas besoin d'importer une bibliothèque externe - dès la définition de la combinaison, avec n cartes qui seraient n*(n-1)/2

Question bonus : Cette même formule permet de calculer la somme du premier n-1 les entiers - vous voyez pourquoi ils sont identiques ? :)

Answer 5

La formule mathématique pour cela est la suivante :

N!/((R!)(N-R)!)

Cela ne devrait pas être difficile de comprendre à partir de là :)