Home > python > Permutations of a list

Permutations of a list

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.

Categories: python Tags: ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: