11

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.
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 builtin list() operator. Note that the resulting list can be huge. All xgenerators 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).
Tags: algorithms

13 comments
Add a comment
Sign in to comment
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 ksized 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/200807/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