Permutation : each of several possible ways in which a set or number of things can be ordered or arranged.
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:
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.
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]]
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
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
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
pivotwith the smallest value possible;
- we must reshuffle the items such that the new
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
The algorithm to implement this consists of the following steps:
- find the largest
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.
- Find the largest index
a[k] < a[l].
- Reverse the sequence from
a[k + 1]up to and including the final element
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]
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.