Table of Contents
1. Introduction
This article presents different algorithms to generate all permutations of a set. Oh no, just another tutorial about this topic, there are already million of them, you think? Maybe... but still I post it for two reasons:
- At first, it's more or less for myself. After never having dealt with this topic before, I noticed that it's far from trivial. This will support me in future to having a fast understanding.
-
Second, even if there are many code snippets on the net about generating all permutations, most of them lack description or proper examples about how they actually work.
The purpose of this article is to present different implementations along with some (hopefully easy understandable) comments about their procedure.
None of them is a new approach or invented by me. They are all taken from the referenced books / articles at the bottom of this site.
2. Permutations (without repetition)
A permutation is an one possible ordering of the elements of an set. Let's say we have a set s of four characters {'A', 'B', 'C', 'D'}. Then a possible permutation is e.g. {'B', 'D', 'C', 'A'}.
This chapter addresses following question: How many different permutations exist for a given set?
Following chapters handle the problem how to generate all these possible permutations?
At first, let's see how many different permutations exist:
- For a given set s with n different elements, there are n possibilities to choose the first item of the permutation.
- For the second item, there are only n-1 elements left to choose from, because one item was already taken away.
- For the third item, then only n-2 items remain. This is repeated for all elements of the set until only 1 item is left for the last item of the permutation.
Summarizing, there are n * (n-1) * (n-2) * ... * 1 = n! different permutations possible!
To calculate all sets, let's dive into a few different algorithms.
3. Algorithms
At first, let's define some prerequisites which share all upcoming implementations:
- The set for which all permutations are generated is an array called items.
- The presented example implementations have char values as elements of the set. This is just for simplicity and no constraint - the algorithms can be easily modified to use elements of other types or vene generics.
- The array is initialized with 'A', 'B', 'C' and so on...
- The function VisitPermutation() is called whenever items contains a new permutation of the set.
- The function Swap() exchanges two elements in the items array.
3.1 Backtracking (taken from [2])
The main idea is to exchange each element to the end of the set and then recursively permute the rest of the set (this is all elements except the last element).
Before examining the algorithm step by step, here is the listing:
{
if (n == 1)
{
VisitPermutation();
}
else
{
for (int c = 0; c < n - 1; c++)
{
Swap(ref items[c], ref items[n - 1]);
Generate(n - 1);
Swap(ref items[c], ref items[n - 1]);
}
Generate(n - 1);
}
}
The function is invoked with the number of elements in the set, e.g. with Generate(3) if items contains the three elements 'A', 'B' and 'C'.
Obviously, the algorithm works for a one-element set. It is started with the call of Generate(1), so the first if-condition is true, the permutation is visited and the function is left. More interesting is the case with two elements so check this case step-by-step:
Example of the backtracking algorithm for a set with two elements 'A' and 'B'
Call Generate(2) with items = ('A' 'B'): Enter loop with c = 0: Swap(items[0], items[1]) = Swap('A', 'B') -> items = ('B' 'A') Generate(1): Visit permutation: ('B' 'A') Swap(items[0], items[1]) = Swap('B', 'A') -> items = ('A' 'B') Loop left. Generate(1): Visit permutation: ('A' 'B')
However, in my opinion the set shall contain at least 3 elements to properly follow the procedure of this algorithm.
Example of the backtracking algorithm for a set with three elements 'A', 'B' and 'C'
Call Generate(3) with items = ('A' 'B' 'C'): Enter loop with c = 0: Swap(items[0], items[2]) = Swap('A', 'C') -> items = ('C' 'B' 'A') (A is exchanged to the end, then permute the first two elements) Generate(2): Swap(items[0], items[1]) = Swap('C', 'B') -> items = ('B' 'C' 'A') Generate(1): Visit permutation: ('B' 'C' 'A') Swap(items[0], items[1]) = Swap('B', 'C') -> items = ('C' 'B' 'A') Generate(1): Visit permutation: ('C' 'B' 'A') Swap(items[0], items[2]) = Swap('C', 'A') -> items = ('A' 'B' 'C') Enter loop with c = 1: Swap(items[1], items[2]) = Swap('B', 'C') -> items = ('A' 'C' 'B') (B is exchanged to the end, then permute the first two elements) Generate(2): Swap(items[0], items[1]) = Swap('A', 'C') -> items = ('C' 'A' 'B') Generate(1): Visit permutation: ('C' 'A' 'B') Swap(items[0], items[1]) = Swap('C', 'A') -> items = ('A' 'C' 'B') Generate(1): Visit permutation: ('A' 'C' 'B') Swap(items[1], items[2]) = Swap('C', 'B') -> items = ('A' 'B' 'C') Loop left. (C is at the end, permutate the first two elements) Generate(2): Swap(items[0], items[1]) = Swap('A', 'B') -> items = ('B' 'A' 'C') Generate(1): Visit permutation: ('B' 'A' 'C') Swap(items[0], items[1]) = Swap('B', 'A') -> items = ('A' 'B' 'C') Generate(1): Visit permutation: ('A' 'B' 'C')
The algorithm is easy to understand and to implement. Also there is no stack problem as the maximum call depth is equal to the number of elements in the set. However the number of swaps is significant: There is a swap of two elements, then the function is called for the other n-1 elements, then the two elements are swapped back. This means for each permutation there are two swaps, expect for the last one because the last recursive call is outside the loop.
Summarized, for an set with n elements, there are 2n! - 2 swaps required.
3.2 Lexicographic permutation algorithm (Algorithm L) (taken from [1])
Additional to above prerequisites, to find all permutations with this algorithm the items in the initial set must be increasing, so:
- items[1] <= items[2] <= ... <= items[n]
The main idea of this algorithm is to 'increase' the current permutation in a way that it is changed by the smallest possible amount.
This procedure is comparable to counting up natural numbers: We check if the last element can be increased. If it cannot be increased, we move on one position to the left and check if this can be increased. So e.g. if we have 13, then we increase the rightmost digit, resulting in 14. For the number 19 we cannot increase the rightmost digit (9 is the largest available digit). So we move one to the left and check if this one can be increased: In this case it can be increased, so 1 is changed to 2, and the 9 is changed to the smallest possible value 0.
Transfered to the permuation algorithm, it works the following way:
- Initialize the set in increasing order: items[0] <= ... <= items[n-1]
- Find the largest element index j (that's the rightmost one) so that items[j] can be increased, that is that items[j] < items[j+1].
In other words: Find the longest suffix that is not increasing. Element at index j is then the element left to this suffix. - Increase items[j] with the smallest possible change. In other words: Find the rightmost element in the suffix that is greater than element at index j
- Note that at this place the suffix is decreasing: items[j+1] >= ... >= items[n-1]
- Reverse items[j+1] ... items[n-1]. This result in the new permutation items[0] ... items[j] items[n] ... items[j+1].
Example of retrieving the next permutation of ('1' '0' '3' '2')
The largest non-increasing suffix is ('3' '2'), thus j = 1 (items[j] is '0'). The rightmost element greater than '0' is '2', so exchange '0' and '2'. This gives ('1' '2' '3' '0'). Note that the suffix ('3' '0') is decreasing. Reversing it gives finally ('1' '2' '0' '3') which is our next permutation.
So here is the listing of a possible implementation:
{
/* trivial case */
if (ItemCount == 1)
{
VisitPermutation();
return;
}
while (true)
{
VisitPermutation();
/* find the largest index j so that items[j] can be increased (longest suffix that is not increasing) */
int j = this.ItemCount - 2;
while (items[j] >= items[j + 1])
{
if (j == 0)
return;
j--;
}
/* increase items[j]: Find the rightmost element in the suffix that is greater than element at index j */
int l = this.ItemCount - 1;
while (items[j] >= items[l])
{
l--;
}
/* swap both items */
Swap(ref items[j], ref items[l]);
/* reverse items[j+1] ... items[n-1]: */
l = this.ItemCount - 1;
int k = j + 1;
while (l > k)
{
Swap(ref items[k], ref items[l]);
k++;
l--;
}
}
}
So let's perform this algorithm by hand for a set with 3 elements to properly follow the procedure:
Example of the lexicographic permutation algorithm for a set with three elements 'A', 'B' and 'C'
Loop 1: Visit permutation: ('A' 'B' 'C') Find index j: j = 1 ('B', longest suffix is 'C') Find index l: l = 2 ('C', that's the rightmost element larger than 'B') Swap elements at indices j = 1 ('B') and l = 2 ('C'): -> ('A' 'C' 'B') Reverse items at indices 2 to 2 -> nothing to do -> ('A' 'C' 'B') Loop 2: Visit permutation: ('A' 'C' 'B') Find index j: j = 0 ('A', longest suffix is 'C' 'B') Find index l: l = 2 ('B', that's the rightmost element larger than 'A') Swap elements at indices j = 0 ('A') and l = 2 ('B'): -> ('B' 'C' 'A') Reverse items at indices 1 to 2 -> ('B' 'A' 'C') Loop 3: Visit permutation: ('B' 'A' 'C') Find index j: j = 1 ('A', longest suffix is 'C') Find index l: l = 2 ('C', that's the rightmost element larger than 'A') Swap elements at indices j = 1 ('A') and l = 2 ('C'): -> ('B' 'C' 'A') Reverse items at indices 2 to 2 -> nothing to do -> ('B' 'C' 'A') Loop 4: Visit permutation: ('B' 'C' 'A') Find index j: j = 0 ('B', longest suffix is 'C' 'A') Find index l: l = 1 ('C', that's the rightmost element larger than 'B') Swap elements at indices j = 0 ('B') and l = 1 ('C'): -> ('C' 'B' 'A') Reverse items at indices 1 to 2 -> ('C' 'A' 'B') Loop 5: Visit permutation: ('C' 'A' 'B') Find index j: j = 1 ('A', longest suffix is 'B') Find index l: l = 2 ('B', that's the rightmost element larger than 'A') Swap elements at indices j = 1 ('A') and l = 2 ('B'): -> ('C' 'B' 'A') Reverse items at indices 2 to 2 -> nothing to do -> ('C' 'B' 'A') Loop 6: Visit permutation: ('C' 'B' 'A') Find index j: j = 0 (whole set is not increasing) -> terminate
3.3 Heap's Algorithm ([3])
Heap's Algorithm is a bit similar to backtracking as it works also in a recursive way. The last element remains fixed while the remaining n-1 elements are permutated. However, the clever choice which elements are swapped differs. Here the main steps of the algorithm:
- Perform following steps n times, ranging from i = 0 to n - 1:
- Fix the last element.
- Generate the permutation for the first n-1 elements. These permutation have all the same last element.
- If n is even, swap the elements at index i with the last element.
- If n is odd, swap the elements at index 0 with the last element.
The key point of Heap's algorithm is the clever exchange of elements. Not only is it correct, meaning that it visits each permutation once, it also has minimal movement of elements: For each permutation one pair is swapped while the position of the other n - 2 elements remain unchanged.
Here the listing of the recursive implementation of Heap's algorithm:
{
if (n == 1)
{
VisitPermutation();
}
else
{
for (int i = 0; i < n - 1; i++)
{
Generate(n - 1);
if ((n % 2) == 0)
{
Swap(ref items[i], ref items[n - 1]);
}
else
{
Swap(ref items[0], ref items[n - 1]);
}
}
Generate(n - 1);
}
}
Again, let's perform the algorithm manually for a three item set to see how it works:
Example of Heap's recursive algorithm for a set with three elements 'A', 'B' and 'C'
Generate(3): Loop i = 0: Generate(2) Loop i = 0: Generate(1): Visit permutation: ('A' 'B' 'C') n = 2 is even: Swap elements at indices 0 and 1 -> ('B' 'A' 'C') Generate(1): Visit permutation: ('B' 'A' 'C') n = 3 is odd: Swap elements at indices 0 and 2 -> ('C' 'A' 'B') Loop i = 1: Generate(2) Loop i = 0: Generate(1): Visit permutation: ('C' 'A' 'B') n = 2 is even -> Swap elements at indices 0 and 1 -> ('A' 'C' 'B') Generate(1): Visit permutation: ('A' 'C' 'B') n = 3 is odd -> Swap elements at indices 0 and 2 -> ('B' 'C' 'A') Generate(2) Loop i = 0: Generate(1): Visit permutation: ('B' 'C' 'A') n = 2 is even -> Swap elements at indices 0 and 1 -> ('C' 'B' 'A') Generate(1): Visit permutation: ('C' 'B' 'A')
4. Miscellaneous
4.1 Additional implemented algorithms
Beside to the three algorithms described above, the zip archive contains also implementations of some other permutation generation algorithms.
In total, following eight algorithms are implemented:
- Backtracking: Described in chapter 3.1.
- Backtracking reversed: Similar to the previous recursive backtracking algorithm, except that each element is exchanged to the first position instead of to the last position.
- Heap' algorithm (recursive): Described in chapter 3.3.
- Heap' algorithm (iterative): An iterative version of Heap's algorithm.
- Algorithm L: Described in chapter 3.2.
- Algorithm P: 'Plain changes permutation algorithm' as described in [1].
- Algorithm T: 'Plain change algorithm' as described in [1]. Uses a precomputed lookup table of size n! containing the information of all transitions.
- Recursive algorithm ("K-Level"): Very interesting, short recursive algorithm taken, see [4].
4.2 Number of items swaps
Just as information, instead of run time measurements, here are the number of item swaps for some input values:
| Number of swaps | ||||||||||||
| n = 1 | n = 2 | n = 3 | n = 4 | n = 5 | n = 6 | n = 7 | n = 8 | n = 9 | n = 10 | n = 11 | n = 12 | |
| Backtracking | 0 | 2 | 10 | 46 | 238 | 1438 | 10078 | 80638 | 725758 | 7257598 | 79833598 | 958003198 |
| Algorithm L | 0 | 1 | 7 | 34 | 182 | 1107 | 7773 | 62212 | 559948 | 5599525 | 61594835 | 739138086 |
| Heap (recursive) | 0 | 1 | 5 | 23 | 119 | 719 | 5039 | 40319 | 362879 | 3628800 | 39916800 | 479001599 |
| Heap (iterative) | 0 | 1 | 5 | 23 | 119 | 719 | 5039 | 40319 | 362879 | 3628800 | 39916800 | 479001599 |
| Algorithm P | 0 | 1 | 5 | 23 | 119 | 719 | 5039 | 40319 | 362879 | 3628799 | 39916799 | 479001599 |
| Algorithm T | 0 | 1 | 5 | 23 | 119 | 719 | 5039 | 40319 | 362879 | 3628799 | 39916799 | N/A |
| Backtracking (reversed) | 0 | 2 | 10 | 46 | 238 | 1438 | 10078 | 80638 | 725758 | 7257598 | 79833598 | 958003198 |
| K-Level recursive | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A |
5. Conclusion & References
I hope you found this article interesting and could learn something! Drop me a line for corrections, hints, criticism, praise ;)
Sunshine, January 2016
References
[1] Donald E. Knuth - The Art Of Computer Programming Pre-Fascicle 2B. A Draft Of Section 7.2.1.2: Generating all permutations[2] Robert Sedgewick - Permutation Generation Methods
[3] Heap's algorithm @ Wikipedia
[4] Recursive algorithm ("K-Level") by Alexander Bogomolny