Algorithme de calcul du coefficient binomial

L’une des meilleures méthodes de calcul du coefficient binomial que j’ai vue suggérée est celle de Mark Dominus . Il est beaucoup moins susceptible de déborder avec des valeurs plus grandes pour N et K que certaines autres méthodes.

 public static long GetBinCoeff(long N, long K) { // This function gets the total number of unique combinations based upon N and K. // N is the total number of items. // K is the size of the group. // Total number of unique combinations = N! / ( K! (N - K)! ). // This function is less efficient, but is more likely to not overflow when N and K are large. // Taken from: http://blog.plover.com/math/choose.html // long r = 1; long d; if (K > N) return 0; for (d = 1; d <= K; d++) { r *= N--; r /= d; } return r; } 

Voici une solution très similaire à Bob Byran, mais vérifie deux autres conditions préalables pour accélérer le code.

  /// 
 /// Calculates the binomial coefficient (nCk) (N items, choose k) /// 
 /// the number items /// the number to choose /// the binomial coefficient public static long BinomCoefficient(long n, long k) { if (k > n) { return 0; } if (n == k) { return 1; } // only one way to chose when n == k if (k > n - k) { k = n - k; } // Everything is symmesortingc around nk, so it is quicker to iterate over a smaller k than a larger one. long c = 1; for (long i = 1; i <= k; i++) { c *= n--; c /= i; } return c; } 

En regardant votre code, il n’est pas étonnant que vous manquiez rapidement de mémoire. Votre méthode divideFactorials appelle la méthode factorielle et utilise comme argument la différence “dénominateur de numérateur”. Cette différence risque fort d’être très grande selon votre code et vous serez coincé dans une très longue boucle dans votre méthode factorielle.

S’il s’agit vraiment de trouver nCk (ce qui, je suppose, est dû à votre commentaire dans votre code), utilisez simplement:

 public static long GetnCk(long n, long k) { long bufferNum = 1; long bufferDenom = 1; for(long i = n; i > Math.Abs(nk); i--) { bufferNum *= i; } for(long i = k; i => 1; i--) { bufferDenom *= i; } return (long)(bufferNom/bufferDenom); } 

Bien sûr, en utilisant cette méthode, vous vous retrouverez très vite en dehors des limites, car un long ne supporte pas les nombres très longs, donc n et k doivent être inférieurs à 20.

En supposant que vous travailliez avec de très grands nombres, vous pouvez utiliser des doublons plutôt que des longs, car les pouvoirs deviennent de plus en plus importants.

Edit: Si vous utilisez de grands nombres, vous pouvez également utiliser la formule de Stirling:

Quand n devient grand, ln (n!) -> n * ln (n) – n.

Mettre ceci dans le code:

 public static double GetnCk(long n, long k) { double buffern = n*Math.Log(n) - n; double bufferk = k*Math.Log(k) - k; double bufferkn = Math.Abs(nk)*Math.Log(Math.Abs(nk)) - Math.Abs(nk); return Math.Exp(buffern)/(Math.Exp(bufferk)*Math.Exp(bufferkn)); } 

Je propose seulement cette réponse, comme vous l’avez dit indépendamment du langage, le code C # est simplement utilisé pour le démontrer. Puisqu’il faut utiliser des nombres importants pour n et k pour que cela fonctionne, je propose ceci comme moyen général de rechercher le coefficient binomial pour les grandes combinaisons.

Pour les cas où n et k sont tous deux inférieurs à environ 200-300, vous devez utiliser la réponse proposée par Victor Mukherjee, car elle est exacte.

Edit2: Edité mon premier code.

Juste pour finir: la bibliothèque de maths standard en C a des implémentations de et de Inn (appelées tgamma et lgamma ), où

(N) = (n-1)!

Le calcul de la bibliothèque est certainement plus rapide et plus précis que la sum des logarithmes. Pour plus d’informations, voir Wikipedia et Mathworld .