HOWTO · Python
How to Generate All Permutations of a List in Python
Learn to generate full and partial permutations of a Python list with itertools.permutations, recursion, and iteration, and understand duplicate results and factorial growth.
On this page
Use Python’s standard library to generate permutations of a list, or choose a recursive or iterative algorithm when you need to customize the process. A permutation is an ordering of selected elements; unlike a combination, the order matters. The number of results grows factorially, so generating every ordering is practical only for modest inputs.
Using the itertools Library
For most tasks, use itertools.permutations. It returns an iterator of tuples, which lets you process results one at a time instead of building a list immediately. By default, r is the length of the input, so each result uses every element. In the example, r=2 selects ordered pairs, and the loop covers each length from one through three.
For the list [1, 2, 3], the program prints:
from itertools import permutations
data = [1, 2, 3]
print("full:", list(permutations(data)))
print("length 2:", list(permutations(data, r=2)))
print("lengths 1 to 3:")
for r in range(1, len(data) + 1):
print(r, list(permutations(data, r)))
full: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
length 2: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
lengths 1 to 3:
1 [(1,), (2,), (3,)]
2 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
3 [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
The r argument sets the number of items in each tuple. To generate all nonempty lengths, call the function once for each r from 1 through the input length, as above. itertools.permutations treats elements by their positions: if a value occurs more than once in the input, corresponding result tuples can repeat.
See the official itertools documentation for the function’s full signature and behavior.
Recursive Function for Permutations
A recursive solution chooses each item in turn, then places it before every permutation of the remaining items. The base case returns a list containing one empty ordering; this makes the construction work for any input length, including zero. This version returns lists rather than tuples and is useful when you want to study or customize the construction.
def permute(data):
if not data:
return [[]]
result = []
for index, item in enumerate(data):
remaining = data[:index] + data[index + 1:]
for tail in permute(remaining):
result.append([item] + tail)
return result
print(permute([1, 2, 3]))
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Each recursive call removes one position, so the remaining input gets smaller until the base case. Repeated values at different positions can still create repeated lists. This implementation stores the full result and makes many recursive calls, so it is best for learning or small inputs; use the standard-library iterator when you do not need custom construction.
Iterative Approach to Generate Permutations
You can also build results by inserting each new item into every position of the partial orderings already collected. The list starts with one empty ordering, then grows by a factor of the next input length at each step. This avoids recursive calls but still stores all results.
def iterative_permute(data):
results = [[]]
for item in data:
next_results = []
for ordering in results:
for index in range(len(ordering) + 1):
next_results.append(ordering[:index] + [item] + ordering[index:])
results = next_results
return results
print(iterative_permute([1, 2, 3]))
[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
Insertion order determines the order in which this method returns its results; it does not change which permutations are generated. Choose it when the step-by-step construction suits your task, and account for the memory needed to keep the complete result.
Conclusion
Use itertools.permutations for a concise, lazy iterator, setting r when you need a particular length. Use recursion or iterative insertion to customize or learn the construction. A list of length n has n! full-length permutations when its positions are distinct, so both processing time and storage for a materialized result grow rapidly. For larger inputs, process the iterator as needed or generate only the lengths and selections relevant to your problem.
FAQ
-
What is a permutation?
It is an ordered selection of items. For example,[1, 2]and[2, 1]are different permutations because their order differs. -
How does
itertools.permutationswork?
It yields tuples of lengthrfrom the input iterable. Ifris omitted, it uses the full input length. The function produces results lazily, but converting the iterator to a list stores every result. -
What happens when the input contains duplicate values?
The function considers positions, not whether values are equal. Repeated input values can therefore produce identical tuples. Converting all results to a set can remove repeated tuples after generation when their elements are hashable, but it does not avoid generating them. To avoid duplicate work, use an algorithm that skips equal choices at each step. -
How many permutations are there?
Forndistinct positions, there aren!full-length permutations. If you choose onlyrpositions, the count isn! / (n - r)!. -
How large an input can I use?
There is no single size limit that fits every machine or task. The factorial count can make even a moderate input expensive to process, and storing all results uses substantial memory. Prefer lazy iteration or a smallerrwhen you do not need every full-length result at once.