Efficiently compute permutations
Tags: python, algorithms
Published: 2018-04-07 21:55:15

---
title: Efficiently compute permutations
published: true
tags: [python, algorithms]
canonical_url: https://mariosangiorgio.github.io/post/permutations/
---

> **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](https://en.wikipedia.org/wiki/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:

```python
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:

```python
>>> 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](https://en.wikipedia.org/wiki/Lexicographical_order) is a good choice that allows us to [generate](https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order) 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:

```python
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:

```python
>>> 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](https://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations). I find [Heap’s algorithm](https://en.wikipedia.org/wiki/Heap%27s_algorithm) particulary interesting because it manages to generate the next permutation by swapping a single pair of elements.

Thanks to [Project Nayuki](https://www.nayuki.io/page/next-lexicographical-permutation-algorithm) for the post that inspired me to look into this algorithm.