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.