3.12. Permutation (advanced)¶
This example is taken from Python Reference Manual. It gives a beautiful illustration of the logic behind Pythonic splices:
def perm(l):
"""Compute the list of all permutations of l"""
if len(l) <= 1:
return [l]
r = []
for i in range(len(l)):
# s = l with the ith element skipped.
s = l[:i] + l[i+1:]
p = perm(s)
for x in p:
# l[i:1+1]: singleton list containing i-th element
r.append(l[i:i+1] + x)
return r
3.12.1. Combinations¶
To implement choose as in “n choose K” try the following (from stackoverflow):
from operator import mul # or mul=lambda x,y:x*y
from fractions import Fraction
def nCk(n,k):
return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )
for n in range(17):
print ' '.join('%5d'%nCk(n,k) for k in range(n+1)).center(100)
Note the Fraction
module is a Python implementation of fractions,
which implements fraction addition and multiplication, treating
fractions as pairs of rationals, so:
Fraction(3.4,1.7)
is an error but the intended computation can be expressed in integer based ratios as:
Fraction(Fraction(34,10),Fraction(17,10))
and is immediately simplified to:
Fraction(2, 1)
Similarly,:
Fraction(1, 3) + Fraction(1, 2)
becomes:
Fraction(5, 6)
So the definition of nCk
really translates the
standard mathematical formula into Python.
Note a more efficient implementation is available from scipy.