Generating all permutations

Backtracking
Recursive

Build all n! permutations of 1 to n in lexicographic order: add an unused item, recurse, then take it back.

Fill the permutation one place at a time. For each empty place, try every item not used yet, fill the rest (recursively), then take the item back to try the next one: backtracking.

Read the full explanation ↓

Time: O(n · n!)
Space: O(n)
Johnsonbaugh, chapter 6
Grimaldi, chapter 1
Horowitz–Sahni, chapter 1

Input:

n=3PDF export

Three items: 3! = 6 permutations, in the order 123, 132, 213, 231, 312, 321.

def permutations(n):
items = list(range(1, n + 1))
used = [False] * n
current = []
rows = []
extend(items, used, current, rows)
return len(rows)
def extend(items, used, current, rows):
if len(current) == len(items):
rows.append(tuple(current))
return
for i in range(len(items)):
if used[i]:
continue
used[i] = True
current.append(items[i])
extend(items, used, current, rows)
current.pop()
used[i] = False

Invariant: current is always a prefix of the remaining permutations, and used marks exactly its items.

Start

current—

The table is still empty.

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

Orange = changed in this step

Call stack

permutations()line 1

Step 1 of 211

Explanation

The idea

Fill the permutation one place at a time. For each empty place, try every item not used yet, fill the rest (recursively), then take the item back to try the next one: backtracking.

If the items are tried in order, the permutations come out in lexicographic order.

Cost

n! permutations of n items each: O(n · n!). That grows very fast (10! = 3628800), which is why n is at most 4 here.

What to watch in the trace

The call tree is the state-space tree: each path from the root to a leaf is one permutation.
If you only need the next permutation (without building them all), see the "next permutation" page.