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.