Permutations and combinations are often required in algorithms that do a complete search of the solution space. They are typically rather large so it's best not to compute them entirely but better to lazily generate them. This recipe uses Python 2.2 generators to create appropriate generator objects, that can be use for example as ranges in for loops.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | ```
#!/usr/bin/env python
__version__ = "1.0"
"""xpermutations.py
Generators for calculating a) the permutations of a sequence and
b) the combinations and selections of a number of elements from a
sequence. Uses Python 2.2 generators.
Similar solutions found also in comp.lang.python
Keywords: generator, combination, permutation, selection
See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/105962
See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66463
See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66465
"""
from __future__ import generators
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 xuniqueCombinations(items, n):
if n==0: yield []
else:
for i in xrange(len(items)):
for cc in xuniqueCombinations(items[i+1:],n-1):
yield [items[i]]+cc
def xselections(items, n):
if n==0: yield []
else:
for i in xrange(len(items)):
for ss in xselections(items, n-1):
yield [items[i]]+ss
def xpermutations(items):
return xcombinations(items, len(items))
if __name__=="__main__":
print "Permutations of 'love'"
for p in xpermutations(['l','o','v','e']): print ''.join(p)
print
print "Combinations of 2 letters from 'love'"
for c in xcombinations(['l','o','v','e'],2): print ''.join(c)
print
print "Unique Combinations of 2 letters from 'love'"
for uc in xuniqueCombinations(['l','o','v','e'],2): print ''.join(uc)
print
print "Selections of 2 letters from 'love'"
for s in xselections(['l','o','v','e'],2): print ''.join(s)
print
print map(''.join, list(xpermutations('done')))
``` |

This recipe provides both combinations and permutations and lazily generates them. You can do arbitrary calculations on the permutation/combination items not just print them.

If you require the complete list of permutations, just use the built-in list() operator. Note that the resulting list can be huge.

All x-generators defined here yield sequences with elements from the original sequence. Their difference is in which elements they take:

xpermutations takes all elements from the sequence, order matters.

xcombinations takes n distinct elements from the sequence, order matters.

xuniqueCombinations takes n distinct elements from the sequence, order is irrelevant.

xselections takes n elements (not necessarily distinct) from the sequence, order matters.

Note that 'distinct' means "different elements in the orginal sequence" and not "different value", i.e.

list(xuniqueCombinations('aabb',2)) is

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

and not

[['a', 'b']].

If your sequence has only items with unique values, you won't notice the difference (no pun intended).

A simple refactoring.I notice that the bodies of xcombinations, xuniqueCombinations, xselections are almost identical. We could refactor as follows:A faster xuniqueCombinations algorithm.Faster permutations.The above is 6x faster on my Pentium P3 3.0 GHz, Python 2.4.1.

Appendum.I meant to say: 6x faster for computing list(permutations(range(8))).Err.On the last line that should have been yield p[:i] + a + p[i:] .much faster...... But it only works on lists:Wrong terminology.(comment continued...)(...continued from previous comment)Comment number 4 code is not working for S = [0,1,2,3]. Comment number 6 code works.

Regarding comment 8 noting the lack of Combination with Replacement: here is a version which (without recursion for the "replacement" case) returns a generator giving the k-sized subsets of a set and allows for combinations with replacement. (It's part of my work with sympy at branch 1766 at github under acct smichr):

There is also a discussion of these issues at http://coding.derkeiler.com/Archive/Python/comp.lang.python/2008-07/msg02095.html but I have not been able to duplicate the results and obtain similar times with what is presented. I'm not sure if I'm doing something wrong or if my machine is just that much slower.

For faster permutation similar to what Connelly and Simone recommended but for a length less than len(L) (i.e. P(L,r)) can try this:

And this is the same code which returns tuples:

This way you can check the results with itertools.permutations() like:

A comparison plot is available here.

I use the following algorithm for permutations:

The algorithm is not as fast as the fast_permutation, but it is faster than the orginal one and than the pure python one available in test_itertools. The main advantage of this code is that the all permutations are generated in logical order: all permutations that starts with the first element come first. This is not the case with fast_permutation. This characteristic is essential to a backtracking problem I have. In fact I have a second version with a additional pruning function reducing the number of permutations generated. The ix parameter indicates which element in the permutation is tested

Because the permutations are generated in logical order, the pruning function is much more optimal to cut away unnecessary permutations before they are generated. As a consequence for backtracking applications, this algorithm is faster than fast_permutation