Generating Permutations

#How does it work?

A permutation is an ordering of the elements. n distinct elements have n! (n factorial) permutations: n choices for the first position, n − 1 for the second, and so on.

With backtracking, each position gets an element not used yet; it is marked as used and we move to the next position. When every position is filled, a permutation is recorded. On the way back the choice is undone and the next element is tried for the same position.

The search tree has n nodes on its first level and n · (n − 1) on the second; it has n! leaves. Trying elements in increasing order produces the permutations in lexicographic order.

#Try it yourself

#Step by step

1. 01Start with an empty chosen list and no element used.
2. 02For each unused element: choose it, mark it used and move to the next position.
3. 03If every position is filled, record the permutation.
4. 04On the way back, undo the choice and the mark (backtracking).

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def permutations(items: list) -> list:
    out, chosen, used = [], [], [False] * len(items)

    def visit() -> None:
        if len(chosen) == len(items):
            out.append(list(chosen))
            return
        for i, x in enumerate(items):
            if used[i]:
                continue
            used[i] = True
            chosen.append(x)
            visit()
            chosen.pop()     # undo the choice (backtrack)
            used[i] = False

    visit()
    return out


for p in permutations([1, 2, 3]):
    print(" ".join(map(str, p)))

#Complexity

n! grows very fast: 10 elements mean 3.6 million permutations, 13 elements over 6 billion. Trying every permutation only works for small n; larger problems need pruning, DP or heuristics.

#When to use it?

Brute-force searches over small orderings (e.g. a travelling salesman with a few cities), generating anagrams, trying every order of test steps and puzzle solvers all generate permutations.

#Practice

Log in to answer questions and save your progress.