How to generate all permutations of a list?

Question

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] 

Answer 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)