Calculate value of n choose k

Solution 1:

Here is my version, which works purely in integers (the division by k always produces an integer quotient) and is fast at O(k):

function choose(n, k)
    if k == 0 return 1
    return (n * choose(n - 1, k - 1)) / k

I wrote it recursively because it's so simple and pretty, but you could transform it to an iterative solution if you like.

Solution 2:

You could use the Multiplicative formula for this:

http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula

Solution 3:

Probably the easiest way to compute binomial coefficients (n choose k) without overflowing is to use Pascal's triangle. No fractions or multiplications are necessary. (n choose k). The nth row and kth entry of Pascal's triangle gives the value.

Take a look at this page. This is an O(n^2) operation with only addition, which you can solve with dynamic programming. It's going to be lightning fast for any number that can fit in a 64-bit integer.

Solution 4:

If you're going to calculate many combinations like this, calculating the Pascal's Triangle is sure the best option. As you already know the recursive formula, I think I can past some code here:

MAX_N = 100
MAX_K = 100

C = [[1] + [0]*MAX_K for i in range(MAX_N+1)]

for i in range(1, MAX_N+1):
    for j in range(1, MAX_K+1):
        C[i][j] = C[i-1][j-1] + C[i-1][j];

print C[10][2]
print C[10][8]
print C[10][3]