Title: Calculate the binomial coefficient "N choose K" efficiently in C#
The binomial coefficient, written and pronounced "n choose k," is the number of ways you can pick k items from a set of n items. For example, suppose you have a deck of 5 cards (n = 5) and you want to know how many different hands of 3 cards you can make (k = 3). If you number the cards 1 through 5, then the possible combinations are:
- 1,2,3
- 1,2,4
- 1,2,5
- 1,3,4
- 1,3,5
- 1,4,5
- 2,3,4
- 2,3,5
- 2,4,5
- 3,4,5
That means .
Notice that the selections are unordered so, for example, 1,2,3 is the same as 3,2,1.
In addition to its combinatorial meaning, the binomial coefficient also gives the coefficient of the xk term in (1 + x)n.
The value of the binomial coefficient is easy to calculate using the formula:
For example:
Unfortunately the factorial function grows very quickly, this formula only lets you calculate values for relatively small values of n and k. For example, 28! is too big to fit in .NET's decimal data type, so you cannot calculate the binomial coefficient when n > 27.
However, the values on the bottom of the equation are big, too. The two values largely cancel out, leaving a result that is much more manageable. The trick is in calculating the binomial coefficient in a way so the intermediate values don't get too big.
To see how to do this, consider the formula and rearrange it a bit like this:
This lets you write "n choose k" in terms of a simple fraction times "n - 1 choose k - 1." If you repeat this process, you can represent the original value as a product of simple fractions like this:
If you group the terms from the right and work backwards, you can successively calculate:
Note that the top value is simply n - (k - 1). Using that value, you can build the others.
Because each of those values represents a binomial coefficient, it must have an integer value. (There can't be 9.7 ways to pick 3 cards from a deck of 5 cards.) That means you can start with the rightmost term and multiply it by each of the terms to the left, getting an integer result at each step.
Here's the C# code to perform this calculation.
decimal result = 1;
for (int i = 1; i <= K; i++)
{
result *= N - (K - i);
result /= i;
}
return result;
Remarkably simple, isn't it?
For example, . This value isn't very large, but to calculate it using factorials you would need to evaluate 28!, which is too big to fit in a decimal variable.
Download the example to experiment with it and to see additional details.
|