I found the following ways to generate permutations on the ASPN: Python Cookbook page.
SLOW (two defs): def xcombinations(items,n): if n == 0: yield[] else: for i in xrange(len(items)): for cc in xcombinations(items[:i]+items[i+1:],n-1): yield [items[i]]+cc def xpermutations(items): return xcombinations(items,len(items)) FAST: def permutations(L): if len(L) <= 1: yield L else: a = [L.pop(0)] for p in permutations(L): for i in range(len(p)+1): yield p[:i] + a + p[i:] The author of the FAST claimed his method was faster, which I wanted to test. I ran the test as follows: import time name = list('python') faster = time.clock() for x in range(10000): map(''.join,list(permutations(name))) total1 = time.clock() - faster print "Total time for faster: ", total1 xperm_start = time.clock() for x in range(10000): map(''.join,list(xpermutations(name))) total2 = time.clock() - xperm_start print "Total time for xperm: ", total2 If you run these tests in the order above, FAST takes about a .1 seconds and slow takes about .17 seconds. BUT if you reverse the order of the test, SLOW takes almost 10 seconds and FAST is about the same! What's more, if you take map, join and list out of the tests (there's no reason for them to be there anyway) the order doesn't matter any more. Without map/join/list, SLOW and FAST are almost indistinguishable at 10K loops. What's going on? ( This was done in Python2.4 ) -- http://mail.python.org/mailman/listinfo/python-list