How to generate all permutations of a list?
There's a function in the standard-library for this: itertools.permutations
.
import itertoolslist(itertools.permutations([1, 2, 3]))
If for some reason you want to implement it yourself or are just curious to know how it works, here's one nice approach, taken from http://code.activestate.com/recipes/252178/:
def all_perms(elements): if len(elements) <=1: yield elements else: for perm in all_perms(elements[1:]): for i in range(len(elements)): # nb elements[0:1] works in both string and list contexts yield perm[:i] + elements[0:1] + perm[i:]
A couple of alternative approaches are listed in the documentation of itertools.permutations
. Here's one:
def permutations(iterable, r=None): # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC # permutations(range(3)) --> 012 021 102 120 201 210 pool = tuple(iterable) n = len(pool) r = n if r is None else r if r > n: return indices = range(n) cycles = range(n, n-r, -1) yield tuple(pool[i] for i in indices[:r]) while n: for i in reversed(range(r)): cycles[i] -= 1 if cycles[i] == 0: indices[i:] = indices[i+1:] + indices[i:i+1] cycles[i] = n - i else: j = cycles[i] indices[i], indices[-j] = indices[-j], indices[i] yield tuple(pool[i] for i in indices[:r]) break else: return
And another, based on itertools.product
:
def permutations(iterable, r=None): pool = tuple(iterable) n = len(pool) r = n if r is None else r for indices in product(range(n), repeat=r): if len(set(indices)) == r: yield tuple(pool[i] for i in indices)
And in Python 2.6 onwards:
import itertoolsitertools.permutations([1,2,3])
(returned as a generator. Use list(permutations(l))
to return as a list.)
The following code with Python 2.6 and above ONLY
First, import itertools
:
import itertools
Permutation (order matters):
print list(itertools.permutations([1,2,3,4], 2))[(1, 2), (1, 3), (1, 4),(2, 1), (2, 3), (2, 4),(3, 1), (3, 2), (3, 4),(4, 1), (4, 2), (4, 3)]
Combination (order does NOT matter):
print list(itertools.combinations('123', 2))[('1', '2'), ('1', '3'), ('2', '3')]
Cartesian product (with several iterables):
print list(itertools.product([1,2,3], [4,5,6]))[(1, 4), (1, 5), (1, 6),(2, 4), (2, 5), (2, 6),(3, 4), (3, 5), (3, 6)]
Cartesian product (with one iterable and itself):
print list(itertools.product([1,2], repeat=3))[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]