How do you generate all the permutations of a list in Python, independently of the type of elements in that list?
For example:
permutations([])
[]
permutations([1])
[1]
permutations([1, 2])
[1, 2]
[2, 1]
permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
There's a function in the standard-library for this: itertools.permutations
.
import itertools
list(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)
This and other recursive solutions have a potential hazard of eating up all the RAM if the permutated list is big enough
They also reach the recursion limit (and die) with large lists
bgbg, dbr: Its using a generator, so the function itself won't eat up memory. Its left to you on how to consume the iterator returned by all_perms (say you could write each iteration to disk and not worry about memory). I know this post is old but I'm writing this for the benefit of everyone who reads it now. Also now, the best way would be to use itertools.permutations() as pointed out by many.
Not just a generator. It's using nested generators, which each yield to the previous one up the call stack, in case that's not clear. It uses O(n) memory, which is good.
PS: I fixed it, with
for i in range(len(elements))
instead offor i in range(len(elements)+1)
. In fact, the singled-out elementelements[0:1]
can be inlen(elements)
different positions, in the result, notlen(elements)+1
.