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

comments powered by Disqus

Featured

Subscribe on YouTube