4.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
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)
Fraction module is a Python implementation of fractions,
which implements fraction addition and multiplication, treating
fractions as pairs of rationals, so:
is an error but the intended computation can be expressed in integer based ratios as:
and is immediately simplified to:
Fraction(1, 3) + Fraction(1, 2)
So the definition of
nCk really translates the
standard mathematical formula into Python.
Note a more efficient implementation is available from scipy.