Generating permutations¶

In this post, we will discuss the problem of generating all permutations of a given set of elements. A permutation is an arrangement of elements in a specific order. The table below shows all permutations of the set {1, 2, 3}:

Permutations of {1, 2, 3}
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

For a set of $n$ elements, there are $n!$ permutations. The problem of generating all permutations of a set of elements is a common problem in computer science and has applications in various fields, such as combinatorial optimization, cryptography, and data analysis.

We generate the permutations of $\{1, 2, \ldots, n\}$ , and use a small helper to print a permutation compactly, as in the slides: [1, 3, 2] is printed as 132.

def show(perm):
    return "".join(map(str, perm))

1. The minimal-change algorithm¶

The minimal-change algorithm is a decrease-by-one algorithm. To generate the $n!$ permutations of $\{1, \ldots, n\}$ , it first generates the $(n-1)!$ permutations of $\{1, \ldots, n-1\}$ , then inserts $n$ in each of the $n$ possible positions of every one of them.

The order of the insertions matters. We insert $n$ from right to left into the first permutation, then switch direction every time we move on to the next permutation of $\{1, \ldots, n-1\}$ . With this rule, each permutation is obtained from the previous one by swapping two adjacent elements, which is why the algorithm is called minimal-change.

An example of generating all permutations of 3 elements:

start with one element: 1
insert 2 into 1 from right to left: $12, 21$
insert 3 into 12 from right to left: $123, 132, 312$
insert 3 into 21 from left to right: $321, 231, 213$

def permutations_minimal_change(n):
    perms = [[1]]
    for k in range(2, n + 1):
        new_perms = []
        right_to_left = True
        for p in perms:
            if right_to_left:
                positions = range(len(p), -1, -1)
            else:
                positions = range(len(p) + 1)
            for pos in positions:
                new_perms.append(p[:pos] + [k] + p[pos:])
            right_to_left = not right_to_left  # switch direction for the next permutation
        perms = new_perms
    return perms


for n in range(1, 5):
    print(n, " ".join(show(p) for p in permutations_minimal_change(n)))

1 1
2 12 21
3 123 132 312 321 231 213
4 1234 1243 1423 4123 4132 1432 1342 1324 3124 3142 3412 4312 4321 3421 3241 3214 2314 2341 2431 4231 4213 2413 2143 2134

We can check the minimal-change property: consecutive permutations differ by a swap of two adjacent elements.

def differs_by_adjacent_swap(p, q):
    diff = [i for i in range(len(p)) if p[i] != q[i]]
    return len(diff) == 2 and diff[1] == diff[0] + 1 and p[diff[0]] == q[diff[1]] and p[diff[1]] == q[diff[0]]


perms = permutations_minimal_change(5)
assert all(differs_by_adjacent_swap(perms[i], perms[i + 1]) for i in range(len(perms) - 1))
print(len(perms), "permutations, each one an adjacent swap away from the next")

120 permutations, each one an adjacent swap away from the next

2. The Johnson-Trotter algorithm¶

The minimal-change algorithm needs all the permutations of $\{1, \ldots, n-1\}$ before it can produce the permutations of $\{1, \ldots, n\}$ . The Johnson-Trotter algorithm produces the same kind of list without generating the smaller permutations: it defines a set of rules that determine the next permutation from the current one.

Each element has a direction, shown by an arrow above it: it points to the left or to the right, as in $\overrightarrow{3}\;\overleftarrow{2}\;\overrightarrow{4}\;\overleftarrow{1}$ .
An element is mobile if its arrow points to a smaller adjacent element. In the example above, 3 and 4 are mobile, while 2 and 1 are not.
To move an element, we swap it with the adjacent element its arrow points to. The arrows move with the elements.

JohnsonTrotter(n):
    initialize the first permutation with ←1 ←2 ... ←n
    while the last permutation has a mobile element do
        find its largest mobile element k
        swap k with the adjacent element k's arrow points to
        reverse the direction of all the elements that are larger than k
        add the new permutation to the list

Let’s take the example of generating all permutations of 3 elements:

start with the permutation $\overleftarrow{1}\;\overleftarrow{2}\;\overleftarrow{3}$
find the largest mobile element: 3 (there are two mobile elements, 3 and 2, and we take the largest one)
swap 3 with the element it is pointing to: $\overleftarrow{1}\;\overleftarrow{3}\;\overleftarrow{2}$
change the direction of all elements greater than 3: no change, since there is no element greater than 3
repeat the process until there is no mobile element.

The following table summarizes the steps of the Johnson-Trotter algorithm for 3 elements:

Permutation	Largest mobile element	Direction change
$\overleftarrow{1}\;\overleftarrow{2}\;\overleftarrow{3}$	3	none
$\overleftarrow{1}\;\overleftarrow{3}\;\overleftarrow{2}$	3	none
$\overleftarrow{3}\;\overleftarrow{1}\;\overleftarrow{2}$	2	$\overrightarrow{3}$
$\overrightarrow{3}\;\overleftarrow{2}\;\overleftarrow{1}$	3	none
$\overleftarrow{2}\;\overrightarrow{3}\;\overleftarrow{1}$	3	none
$\overleftarrow{2}\;\overleftarrow{1}\;\overrightarrow{3}$	no mobile element

In the implementation, the directions are stored in a list direction next to the permutation: direction[i] is -1 if the element at position i points to the left and +1 if it points to the right, so i + direction[i] is the position of the element it points to.

LEFT, RIGHT = -1, 1


def show_arrows(perm, direction):
    return " ".join(("←" if d == LEFT else "→") + str(x) for x, d in zip(perm, direction))


def johnson_trotter(n, trace=False):
    perm = list(range(1, n + 1))
    direction = [LEFT] * n
    result = [perm.copy()]

    while True:
        # find the largest mobile element
        mobile = None  # position of the largest mobile element
        for i in range(n):
            j = i + direction[i]  # position of the element it points to
            if 0 <= j < n and perm[i] > perm[j]:
                if mobile is None or perm[i] > perm[mobile]:
                    mobile = i
        if mobile is None:
            if trace:
                print(show_arrows(perm, direction), "  no mobile element")
            break

        k = perm[mobile]
        if trace:
            print(show_arrows(perm, direction), "  largest mobile:", k)

        # swap k with the element it points to; the arrows move with the elements
        j = mobile + direction[mobile]
        perm[mobile], perm[j] = perm[j], perm[mobile]
        direction[mobile], direction[j] = direction[j], direction[mobile]

        # reverse the direction of all the elements larger than k
        for i in range(n):
            if perm[i] > k:
                direction[i] = -direction[i]

        result.append(perm.copy())

    return result

Tracing the algorithm for $n = 3$ reproduces the table above:

perms = johnson_trotter(3, trace=True)
print(" ".join(show(p) for p in perms))

←1 ←2 ←3   largest mobile: 3
←1 ←3 ←2   largest mobile: 3
←3 ←1 ←2   largest mobile: 2
→3 ←2 ←1   largest mobile: 3
←2 →3 ←1   largest mobile: 3
←2 ←1 →3   no mobile element
123 132 312 321 231 213

Comparing the two algorithms¶

Both algorithms generate every permutation exactly once. They even generate them in the same order, so the Johnson-Trotter list is also a minimal-change list:

from itertools import permutations
from math import factorial

for n in range(1, 8):
    jt = johnson_trotter(n)
    assert jt == permutations_minimal_change(n)
    assert len(jt) == factorial(n)
    assert sorted(map(tuple, jt)) == sorted(permutations(range(1, n + 1)))
print("Same order for n = 1, ..., 7")

print(" ".join(show(p) for p in johnson_trotter(4)))

Same order for n = 1, ..., 7
1234 1243 1423 4123 4132 1432 1342 1324 3124 3142 3412 4312 4321 3421 3241 3214 2314 2341 2431 4231 4213 2413 2143 2134

The difference is in what each algorithm needs to keep. The minimal-change algorithm builds the complete list of permutations of $\{1, \ldots, n-1\}$ before producing anything. Johnson-Trotter only needs the current permutation and its arrows to compute the next one; the function above collects the permutations into a list only so we can print them. Finding the largest mobile element scans the permutation, so each step takes $O(n)$ time and the whole algorithm runs in $O(n \cdot n!)$ .