How do I generate all permutations of a list?

How do I generate all the permutations of a 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]

For Python 2.6 onwards:

import itertools
itertools.permutations([1, 2, 3])

This returns as a generator. Use list(permutations(xs)) to return as a list.

Leave a Comment