Python Adventures

Update (20120321): The methods presented here can generate all the permutations. However, the permutations are not ordered lexicographically. If you need the permutations in lexicographical order, refer to this post.

Problem

You need all the permutations of a list.

Solution

With generators:

#!/usr/bin/env python

def perms01(li):
    if len(li)         yield li
    else:
        for perm in perms01(li[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + li[0:1] + perm[i:]

for p in perms01(['a','b','c']):
    print p

Output:

['a', 'b', 'c']
['b', 'a', 'c']
['b', 'c', 'a']
['a', 'c', 'b']
['c', 'a', 'b']
['c', 'b', 'a']

This tip is from here.

Without generators:

def perms02(l):
    sz = len(l)
    if sz         return [l]
    return [p[:i]+[l[0]]+p[i:] for i in xrange(sz) for p in perms02(l[1:])]

for p in perms02(['a','b','c']):
    print p

Output:

['a', 'b', 'c']
['a', 'c', 'b']
['b', 'a', 'c']
['c', 'a', 'b']
['b', 'c', 'a']
['c', 'b', 'a']

This tip is from here.

The two outputs contain the same elements in a different order.

Notes

If S is a finite set of n elements, then there are n! permutations of S. For instance, if we have 4 letters (say a, b, c, and d), then we can arrange them in 4! = 4 * 3 * 2 * 1 = 24 different ways.