4.9. Combination

Let’s implement a mathematical formula for the number of combinations of r things that can be chosen from a set of n things.

This is called n choose r or ncr for short. Here is some code implementing it, using the operator module:

import operator as op
def ncr(n, r):
    r = min(r, n-r)
    if r == 0: return 1
    # if n = 7 and r = 3, 7 * 6 * 5,  or n!/(n-r)!
    numer = reduce(op.mul, xrange(n, n-r, -1))
    # if r = 3, 3 * 2 * 1 or r!
    denom = reduce(op.mul, xrange(1, r+1))
    return numer//denom

The function:samp:reduce is builtin Python function. The way reduce works is that it applies a two-place operation to the first two elements and then applies the function again to the result of the first application and the third element of the list and so on. So that if we defined a function:

def times (x,y):
    return x * y

then:

>>> reduce(times, [1,2,3,4])
24

Of course times is utterly unncessary as a function, since we have the built in Python operator * which does exactly the same thing. The only use for times is in a call to reduce, where it is necessary because:

>>> reduce(*, [1,2,3])
reduce(*,[1,2,3])
        ^
SyntaxError: invalid syntax

The operator module provides names for many Python operators which have special syntactic properties, so that they can be used in contexts where they would otherwise be illegal. The analogue of * is op.mul. Using op.mul is more efficient than using times as deined above.