Permutation : each of several possible ways in which a set or number of things can be ordered or arranged.

The problem

Given several items, it could be interesting to find all the possible ways we can arrange them. For instance, the string ABC has six permutations: ABC, ACB, BAC, BCA, CAB, CBA. Note that the number of permuration is the factorial of the number of items. This happens because we can pick any of the items as the first one, we have #items - 1 choices for the second and so on till we reach the last item with a single choice.

A recursive solution

We could compute all the permutations recursively, as shown in this Python function:

def permutations(items):
  if len(items) == 1:
    return [items]
  result = []
  # We keep only the distinct items to avoid returning duplicates
  for item in list(set(items)):
    others = items[:]
    others.remove(item)
    for permutation in permutations(others):
      # Note: if we want lexicographical order we should insert in front
      # assuming that items are sorted
      permutation.append(item)
      result.append(permutation)
  return result

We could execute this and get the results we expected:

>>> permutations([1,2,3])
[[3, 2, 1], [2, 3, 1], [3, 1, 2], [1, 3, 2], [2, 1, 3], [1, 2, 3]]
>>> permutations([1,2,1])
[[2, 1, 1], [1, 2, 1], [1, 1, 2]]

A better approach

This solution works, it is nice and simple but it isn’t very efficient: it requires us to create a lot of copies of the list of items so that we can pass them into the next recursive step. Another drawback is that this function computes (and keeps in memory) all the permutations, which it’s a waste if we only need a few of them.

We could look at this from another angle and ask ourselves if there is any way we could take a list of items and find out only the next permutation, whatever that means.

If we talk about the next permutation we kind of imply that there is an order between them. In principle the definition of permutations doesn’t imply any order, but we could always add a constraint ourselves and require some ordering. Using the lexicographical order is a good choice that allows us to generate the next permutation for a given list of items.

Going back to our initial example, we could start from ABC, reorganize the items to get ACB, do it another time to obtain BAC, and so on. This will allow us to compute all the permutations, but this time one of a time and without unnecessary copies of the list.

The first list in lexicographical order has all its items in non-decreasing order: forall i: items[i] <= items[i+1]. In our example, we have ABC and A < B and B < C. On the opposite, the last item has all its items in non-incresing order: forall i: items[i] >= items[i+1]. In our example, we have CBA and C > B and B > A.

Our algorithm needs to make us transition from these two extremes by rearranging the elements such that each permutation ‘increases’ the sequence by the minimal amount. The key observation is that we want to look for the longest suffix in non decreasing order (i.e. that is already the biggest possible). Let’s call it suffix. In order to make some progress we need to consider all the items in suffix and the one immediately before it, which we call pivot. If we start from 0125430 we could split the string in prefix = 01, pivot = 2, and suffix = 5430.

We’re looking for the minimal change so we shouldn’t touch prefix. If we do we’ll get a bigger change than the one we want. We can only move pivot and the items in suffix. We also must do that satisfying these two conditions to be able to advance to the next permutation in lexicographical order:

• we need to replace pivot with the smallest value possible;
• we must reshuffle the items such that the new suffix is minimal.

We can satisfy the first condition by replacing pivot with the smallest item in suffix greater than pivot itself. Taking a smaller value would mean going backwards, taking a bigger value would mean going too far. In our example we will get prefix = 01, pivot = 3 and suffix = 5420.

This is a step in the right direction, but we still have satisfy the second condition. We’ve got a maximal suffix, we can make it minimal by simply reversing it, which has the effect of turning the non-decreasing order to the non-increasing order we’re after. In our example we will get prefix = 01, pivot = 3 and suffix = 0245. We’re done, the next permutation is 0130245

The algorithm

The algorithm to implement this consists of the following steps:

1. find the largest k such that a[k] < a[k+1]. If we cannot find it, the item we’re looking at is already the last in lexicographical order. We could find the next item by just wrap around and generate the first permutation in lexicographical order.
2. Find the largest index l greater than k such that a[k] < a[l].
3. Swap a[k] and a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

In code this looks like:

def next_permutation(items):
  n = len(items)
  # Find pivot
  k = None
  for i in range(n-1):
    if(items[i] < items[i+1]):
      k = i
  if k is None:
    # items is maximal. We need to wrap around
    return None
  # Find new pivot
  for i in range(k, n):
    if(items[k] < items[i]):
      l = i
  # Swap pivot
  items[k], items[l] = items[l], items[k]
  # Reverse suffix
  for i in range(k+1, int((k+1+n)/2)):
    items[i], items[n-i] = items[n-i], items[i]
  return items

And we can use it as follows:

>>> permutation = [1,2,3]
>>> while permutation != None:
... print(permutation)
... permutation = next_permutation(permutation)
...
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Other approaches

This is not the only possible approach to generating permutations. There are in fact several other algorithms. I find Heap’s algorithm particulary interesting because it manages to generate the next permutation by swapping a single pair of elements.

Thanks to Project Nayuki for the post that inspired me to look into this algorithm.