Calculating C(n,r) efficiently

2012-10-27

The number of ways of choosing $r$ items from a collection of $n$ identical items is referred to as $C(n,r)$, ${}^{n}C_{r}$ or $ n \choose r $</span> and is a fundamental counting operation. <span>$ n \choose r $ is given by

\[ {n \choose r} = \frac {n(n-1)(n-2)...(n-r+1)} {r(r-1)...1} \]

or, equivalently, using factorials,

\[ {n \choose r} = \frac { n! }{ r! (n-r)! } \]

One implementation would be to compute the constituent factorials and the perform the multiplication and division on them. But this is bad for 2 reasons

It is slow.
For even decent problems like C(100, 2), where the answer is 4950, the intermediate factorials are very large. 100! is approximately 9.33e57 and hence, languages that do not have numeric types to hold that kind of a number will overflow, wrecking havoc - all for a result that fits well within 2 bytes!

A better implementation should use this recurrence:

\[ {n \choose r} = \frac{n}{r} { {n-1} \choose {r-1} } \]

with

\[ {n \choose 1} = n \] \[ {n \choose 0} = 1 \] \[ {0 \choose r} = 0 \]

so, a recursive implementation in Python would look like

def comb(n, r):
    '''
    Find the number of ways r items can be chosen from a pool of n
    identical items, with n >= r

    '''
    if r > n or n == 0:
        return 0
    if r == 0:
        return 1
    return n * comb(n - 1, r - 1) / r

An iterative implementation is also not very difficult to arrive at:

def comb(n, r):
    '''
    Find the number of ways r items can be chosen from a pool of n
    identical items, with n >= r

    '''
    if r > n:
        return 0
    result = 1
    for i in xrange(r):
        result *= n
        result /= (i + 1)
        n -= 1
    return result