This article introduces common algorithms for permuation generation.

Algorithm 1: Backtracking Algorithm

def perm_backtrack(l):
    '''
    Switch-to-end backtracking.
    '''
    def dfs(l, n):
        if n == 0:
            print(l)
            return
        for j in range(n):
            l[n - 1], l[j] = l[j], l[n - 1]
            dfs(l, n - 1)
            l[n - 1], l[j] = l[j], l[n - 1]
    dfs(l, len(l))

The idea is, when generating permutation of length n, first switch each element to the last index and then call recursion on length n - 1.

To work correctly, the content of the list needs to be kept the same as original when the call returns. That’s why we use backtracking, as shown by the second swap.

Algorithm 2: Nested Rotation Algorithm

def perm_rotation(l):
    '''
    Nested rotation.
    '''
    def dfs(l, i):
        if i == len(l):
            print(l)
            return
        for _ in range(len(l) - i):
            dfs(l, i + 1)
            l.append(l.pop(i))
    dfs(l, 0)

I came up with this function after inspired by a combinatorial problem. I like its succinctness so much. This is probably the shortest permutation generator one can ever write.

The idea is to rotate sublists at different levels. This not only fills the last position with different values, but also restores the sublists to their original state when the recursion exits. Thanks to the rounding nature of rotation, there is not any backtracking artifact (such as the second swap in Algorithm 1).

The problem with this algorithm is that it doesn’t work well on arrays, because arrays don’t support rotation very well (\(O(n)\) instead of \(O(1)\) time). However, it’d be OK with a linked list. Also, if efficiency is not an issue, this function is probably the easiest to write due to its beautiful nature.

Algorithm 3: Steinhaus–Johnson–Trotter Algorithm

def perm_sjt(l):
    '''
    Steinhaus–Johnson–Trotter algorithm (plain changes).
    '''
    n = len(l)
    idx   = [i          for i in range(n)]
    pos   = [i          for i in range(n)]
    count = [n - 1 - i  for i in range(n)]
    step  = [1          for i in range(n)]
    cur = 0
    while True:
        print(l)
        while count[cur] == 0:
            step[cur] = -step[cur]
            count[cur] = n - 1 - cur
            cur = cur + 1
            if cur == n:
                return
        cpos, npos = pos[cur], pos[cur] + step[cur]
        idx[cpos], idx[npos] = idx[npos], idx[cpos]
        l[cpos], l[npos] = l[npos], l[cpos]
        pos[idx[cpos]], pos[idx[npos]] = cpos, npos
        count[cur] -= 1
        cur = 0

The code I came up with here isn’t the original SJT algorithm, but it shares the same idea of exchanging adjacent elements. It looks similar to Even’s speedup, but has a different implementation.

The good point is that only one exchange needs to be done for each permutation (the idx list is not needed if data type is numeric). The while loop executes only when Element 0 “hits the end”, which happens \(1/n\) of the time. Thus the while loop overhead is \(O(1 / n * n) = O(1)\). This means the time needed for each permutation is constant (amortized).

Algorithm 4: Heap’s Algorithm

def perm_heap(l):
    '''
    Heap's algorithm.
    '''
    def dfs(l, n):
        if n == 0:
            print(l)
            return
        for i in range(n):
            dfs(l, n - 1)
            pos = 0 if n % 2 else i
            l[pos], l[n - 1] = l[n - 1], l[pos]
    dfs(l, len(l))

This is an amazing algorithm which reduces the number of element exchanges down to 1. This means there is no backtracking (as you can compare it with Algorithm 1). It exchanges the last element with:

  • The first element, if array length is odd.

  • The i-th element, if array length is even.

It’s not obvious why this works correctly, so let’s demystify it.

  • When n == 1, the algorithm starts with [0] and ends with [0].

  • When n == 2, the algorithm starts with [0, 1] and ends with [1, 0]:

    0, 1        # i == 0, swap l[0] with l[1]
1, 0        # i == 1, swap l[1] with l[1]
1, 0

  • When n == 3, the algorithm starts with [0, 1, 2] and ends with [0, 1, 2]:

    0, 1, 2     # n == 2 recursion
1, 0, 2     # i == 0, swap l[0] with l[2]
2, 0, 1     # n == 2 recursion
0, 2, 1     # i == 1, swap l[0] with l[2]
1, 2, 0     # n == 2 recursion
2, 1, 0     # i == 2, swap l[0] with l[2]
0, 1, 2

  • When n == 4, the algorithm starts with [0, 1, 2, 3] and ends with [3, 0, 1, 2]:

    0, 1, 2, 3  # n == 3 recursion
0, 1, 2, 3  # i == 0, swap l[0] with l[3]
3, 1, 2, 0  # n == 3 recursion
3, 1, 2, 0  # i == 1, swap l[1] with l[3]
3, 0, 2, 1  # n == 3 recursion
3, 0, 2, 1  # i == 2, swap l[2] with l[3]
3, 0, 1, 2  # n == 3 recursion
3, 0, 1, 2  # i == 3, swap l[3] with l[3]
3, 0, 1, 2

We may guess that:

  • The algorithm keeps the subarray intact when its length n is odd, and it correctly computes permutation with length n.

  • The algorithm rotates the subarray one place to the right when its length n is even, and it correctly computes permutation with length n.

This is true and can be proved using induction:

  1. The algorithm keeps the subarray intact when n is 1. And the algorithm correctly generates permutation with length 1.

  2. Suppose the algorithm keeps the subarray intact when n == 2m - 1. We prove the algorithm rotates the subarray one place to the right when n == 2m.

    We prove by drawing a table for when n == 2m:

    0,      1, 2, ..., 2m - 3, 2m - 2, 2m - 1       # n == 2m - 1 recursion
0,      1, 2, ..., 2m - 3, 2m - 2, 2m - 1       # i == 0, swap l[0] with l[2m - 1]
2m - 1, 1, 2, ..., 2m - 3, 2m - 2, 0            # n == 2m - 1 recursion
2m - 1, 1, 2, ..., 2m - 3, 2m - 2, 0            # i == 1, swap l[1] with l[2m - 1]
2m - 1, 0, 2, ..., 2m - 3, 2m - 2, 1            # n == 2m - 1 recursion
2m - 1, 0, 2, ..., 2m - 3, 2m - 2, 1            # i == 2, swap l[2] with l[2m - 1]
2m - 1, 0, 1, ..., 2m - 3, 2m - 2, 2            # n == 2m - 1 recursion
2m - 1, 0, 1, ..., 2m - 3, 2m - 2, 2            # ...
...
2m - 1, 0, 1, ..., 2m - 4, 2m - 2, 2m - 3       # n == 2m - 1 recursion
2m - 1, 0, 1, ..., 2m - 4, 2m - 2, 2m - 3       # i == 2m - 2, swap l[2m - 2] with l[2m - 1]
2m - 1, 0, 1, ..., 2m - 4, 2m - 3, 2m - 2       # n == 2m - 1 recursion
2m - 1, 0, 1, ..., 2m - 4, 2m - 3, 2m - 2       # i == 2m - 1, swap l[2m - 1] with l[2m - 1]
2m - 1, 0, 1, ..., 2m - 4, 2m - 3, 2m - 2

    The result proves the claim.

    Please also note that the algorithm enumerates all possible values in the last element and correctly generates n-permulation from (n-1)-permutation.

  3. Suppose the algorithm rotates the subarray one place to the right when n == 2m. We prove the algorithm keeps the subarray intact when n == 2m + 1.

    We prove by drawing a table for when n == 2m + 1:

    0     , 1,      2,  ..., 2m - 2, 2m - 1, 2m     # n == 2m recursion
2m - 1, 0,      1,  ..., 2m - 3, 2m - 2, 2m     # i == 0, swap l[0] with l[2m]
2m    , 0,      1,  ..., 2m - 3, 2m - 2, 2m - 1 # n == 2m recursion
2m - 2, 2m,     0,  ..., 2m - 4, 2m - 3, 2m - 1 # i == 1, swap l[0] with l[2m]
2m - 1, 2m,     0,  ..., 2m - 4, 2m - 3, 2m - 2 # n == 2m recursion
2m - 3, 2m - 1, 2m, ..., 2m - 5, 2m - 4, 2m - 2 # i == 2, swap l[0] with l[2m]
2m - 2, 2m - 1, 2m, ..., 2m - 5, 2m - 4, 2m - 3 # ...
...
2     , 3,      4,  ..., 2m    , 0     , 1      # n == 2m recursion
0     , 2,      3,  ..., 2m - 1, 2m    , 1      # i == 2m - 1, swap l[0] with l[2m]
1     , 2,      3,  ..., 2m - 1, 2m    , 0      # n == 2m recursion
2m    , 1,      2,  ..., 2m - 2, 2m - 1, 0      # i == 2m, swap l[0] with l[2m]
0     , 1,      2,  ..., 2m - 2, 2m - 1, 2m

    The result proves the claim.

    Please also note that the algorithm enumerates all possible values in the last element and correctly generates n-permulation from (n-1)-permutation.

This concludes the proof.

References