Improved Combinations with the BigInteger Data Type: Listing 2.
An efficient Choose method.
public static BigInteger Choose(int n, int k)
{
if (n < 0 || k < 0)
throw new Exception("Negative argument in Choose");
if (n < k) return 0; // special
if (n == k) return 1; // short-circuit
int delta, iMax;
if (k < n - k) // ex: Choose(100,3)
{
delta = n - k; iMax = k;
}
else // ex: Choose(100,97)
{
delta = k; iMax = n - k;
}
BigInteger ans = delta + 1;
for (int i = 2; i <= iMax; ++i)
ans = (ans * (delta + i)) / i;
return ans;
}
About the Author
Dr. James McCaffrey works for Microsoft Research in Redmond, Wash. He has worked on several Microsoft products including Azure and Bing. James can be reached at [email protected].