A Simple, Efficient P(n,k) Algorithm
September 22, 2009
Jeffrey A. Johnson’s SEPA: A Simple, Efficient Permutation Algorithm is indeed a fast and simple way to generate all the permutations of n items or P(n) in lexicographic order. In this article, I describe a similar algorithm for generating partial permutations of n items taken k at a time, which we denote as P(n, k).
SEPA Explained
Johnson discovered that a set of logical steps could be taken from one permutation to the next. Repeatedly calling the algorithm on the last output obtained generates all permutations in sorted order.
It works by first scanning for the rightmost ascent or pair of numbers where the first number is less than the one immediately after it.
P_{i} | a_{0} | a_{1} | a_{2} | a_{3} | a_{4} |
⋮ | ⋮ | ||||
17 | 0 | 3 | 4 | 2 | 1 |
18 | 0 | 4 | 1 | 2 | 3 |
19 | 0 | 4 | 1 | 3 | 2 |
20 | 0 | 4 | 2 | 1 | 3 |
21 | 0 | 4 | 2 | 3 | 1 |
22 | 0 | 4 | 3 | 1 | 2 |
23 | 0 | 4 | 3 | 2 | 1 |
24 | 1 | 0 | 2 | 3 | 4 |
⋮ | ⋮ |
If no ascent is found, then all numbers are in descending order and this is the last, lexicographic permutation.
Otherwise, the number at the start of the ascent is swapped with the smallest higher number to its right.
P’_{i} | a_{0} | a_{1} | a_{2} | a_{3} | a_{4} |
⋮ | ⋮ | ||||
17′ | 0 | 4 | 3 | 2 | 1 |
18′ | 0 | 4 | 1 | 3 | 2 |
19′ | 0 | 4 | 2 | 3 | 1 |
20′ | 0 | 4 | 2 | 3 | 1 |
21′ | 0 | 4 | 2 | 3 | 1 |
22′ | 0 | 4 | 3 | 2 | 1 |
23′ | 1 | 4 | 3 | 2 | 0 |
24′ | 1 | 0 | 2 | 4 | 3 |
⋮ | ⋮ |
Finally, all the numbers to the right (which will be in descending order) are ‘flipped’ or reversed (to ascending order). The resulting array is the next permutation.
P(n) to P(n,k)
To begin generating P(n,k), let’s take a look at the first few permutations of 5 elements taken 3 at a time, P(5,3) and compare this with P(5):
P_{i} | a_{0} | a_{1} | a_{2} |
0 | 0 | 1 | 2 |
1 | 0 | 1 | 3 |
2 | 0 | 1 | 4 |
3 | 0 | 2 | 1 |
4 | 0 | 2 | 3 |
5 | 0 | 2 | 4 |
⋮ | ⋮ |
If we look carefully at the first 3 values of P(5), a_{0}, a_{1} and a_{2}, we actually find P(5, 3). Except, to get P(5, 3) from P(5) we need to ‘skip’ a few permutations.
P(5)_{i} | a_{0} | a_{1} | a_{2} | a_{3} | a_{4} |
0 | 0 | 1 | 2 | 3 | 4 |
1 | 0 | 1 | 2 | 4 | 3 |
2 | 0 | 1 | 3 | 2 | 4 |
3 | 0 | 1 | 3 | 4 | 2 |
4 | 0 | 1 | 4 | 2 | 3 |
5 | 0 | 1 | 4 | 3 | 2 |
6 | 0 | 2 | 1 | 3 | 4 |
7 | 0 | 2 | 1 | 4 | 3 |
8 | 0 | 2 | 3 | 1 | 4 |
9 | 0 | 2 | 3 | 4 | 1 |
10 | 0 | 2 | 4 | 1 | 3 |
⋮ | ⋮ |
Basically, we can safely ‘skip’ all permutations in P(5) that don’t permute the first 3 positions. For purposes of discussion, we designate the k^{th} or 3^{rd} position, a_{2} as the ‘edge’.
P_{i} | a_{0} | a_{1} | a_{2} | a_{3} | a_{4} |
0 | 0 | 1 | 2 | 3 | 4 |
2 | 0 | 1 | 3 | 2 | 4 |
4 | 0 | 1 | 4 | 2 | 3 |
6 | 0 | 2 | 1 | 3 | 4 |
8 | 0 | 2 | 3 | 1 | 4 |
10 | 0 | 2 | 4 | 1 | 3 |
12 | 0 | 3 | 1 | 2 | 4 |
14 | 0 | 3 | 2 | 1 | 4 |
16 | 0 | 3 | 4 | 1 | 2 |
18 | 0 | 4 | 1 | 2 | 3 |
20 | 0 | 4 | 2 | 1 | 3 |
⋮ | ⋮ |
Another way to look at this is that in generating P(n) using Johnson’s SEPA, we look for the rightmost ascent. In P(n, k) generation, we’re only interested in ascents at the ‘edge’ or to the left of the ‘edge’.
We first assume that the edge contains our ‘ascent’ and look for the next higher number to the right of the edge.
P_{i} | a_{0} | a_{1} | a_{2} | a_{3} | a_{4} |
0 | 0 | 1 | 2 | 3 | 4 |
⋮ | 0 | 1 | 3 | 2 | 4 |
0 | 1 | 4 | 2 | 3 | |
0 | 2 | 1 | 3 | 4 | |
0 | 2 | 3 | 1 | 4 | |
0 | 2 | 4 | 1 | 3 | |
0 | 3 | 1 | 2 | 4 | |
0 | 3 | 2 | 1 | 4 | |
0 | 3 | 4 | 1 | 2 | |
0 | 4 | 1 | 2 | 3 | |
0 | 4 | 2 | 1 | 3 | |
0 | 4 | 3 | 1 | 2 | |
⋮ |
If all numbers to the right of the edge are smaller, then we know that the ascent must be to the left of the edge.
However, unlike with regular P(n) generation, at this point all numbers to the right of the edge will be in ascending order. We know this since we began with all numbers in ascending order, and all our operations at this point simply swap the value at the edge with the next higher number.
Fortunately, by simply reversing everything to the right of the edge we return to a state similar to P(n) where all values to the right of the actual ascent are in descending order. We can now proceed as with the regular SEPA.
P_{i} | a_{0} | a_{1} | a_{2} | a_{3} | a_{4} |
0 | 0 | 1 | 2 | 3 | 4 |
⋮ | 0 | 1 | 3 | 2 | 4 |
0 | 1 | 4 | 3 | 2 | |
0 | 2 | 1 | 3 | 4 | |
0 | 2 | 3 | 1 | 4 | |
0 | 2 | 4 | 3 | 1 | |
0 | 3 | 1 | 2 | 4 | |
0 | 3 | 2 | 1 | 4 | |
0 | 3 | 4 | 2 | 1 | |
0 | 4 | 1 | 2 | 3 | |
0 | 4 | 2 | 1 | 3 | |
0 | 4 | 3 | 2 | 1 | |
⋮ |
A Simple, Efficient Algorithm for Generating P(n, k)
This leads us to the adapted algorithm for generating permutations of n items taken k at a time, in lexicographic order.
def a = { 0, 1, 2 … (n - 1) } def edge = k - 1 // find j in (k…n-1) where a_{j} > a_{edge} j = k while j < n and a_{edge} >= a_{j}, ++j if j < n { swap a_{edge}, a_{j} } else { reverse a_{k} to a_{n-1} // find rightmost ascent to left of edge i = edge - 1 while i > 0 and a_{i} >= a_{i}+1, --i if i < 0, // no more permutations return 0 // find j in (n-1…i+1) where a_{j} > a_{i} j = n - 1 while j > i and a_{i} >= a_{j} --j swap a_{i}, a_{j} reverse a_{i+1} to a_{n-1} } output a_{0}, a_{1} … a_{k-1}
SEP(n,k) Algorithm Illustrated
To show how the algorithm works, let’s step through the major operations showing the state of the array a at each step.
P_{i} | a_{0} | a_{1} | a_{2} | a_{3} | a_{4} | Step |
0 | 0 | 1 | 2 | 3 | 4 | swap a_{2}, a_{3} |
1 | 0 | 1 | 3 | 2 | 4 | swap a_{2}, a_{4} |
2 | 0 | 1 | 4 | 2 | 3 | reverse a_{3..4} |
0 | 1 | 4 | 3 | 2 | swap a_{1}, a_{4} | |
0 | 2 | 4 | 3 | 1 | reverse a_{2..4} | |
3 | 0 | 2 | 1 | 3 | 4 | swap a_{2}, a_{3} |
4 | 0 | 2 | 3 | 1 | 4 | swap a_{2}, a_{4} |
5 | 0 | 2 | 4 | 1 | 3 | reverse a_{3..4} |
0 | 2 | 4 | 3 | 1 | swap a_{1}, a_{3} | |
0 | 3 | 4 | 2 | 1 | reverse a_{2..4} | |
6 | 0 | 3 | 1 | 2 | 4 | swap a_{2}, a_{3} |
7 | 0 | 3 | 2 | 1 | 4 | swap a_{2}, a_{4} |
8 | 0 | 3 | 4 | 1 | 2 | reverse a_{3..4} |
0 | 3 | 4 | 2 | 1 | swap a_{1}, a_{2} | |
0 | 4 | 3 | 2 | 1 | reverse a_{2..4} | |
9 | 0 | 4 | 1 | 2 | 3 | swap a_{2}, a_{3} |
10 | 0 | 4 | 2 | 1 | 3 | swap a_{2}, a_{4} |
11 | 0 | 4 | 3 | 1 | 2 | reverse a_{3..4} |
0 | 4 | 3 | 2 | 1 | swap a_{0}, a_{4} | |
1 | 4 | 3 | 2 | 0 | reverse a_{1..4} | |
12 | 1 | 0 | 2 | 3 | 4 | swap a_{2}, a_{3} |
⋮ | ⋮ | ⋮ |
Java Implementation
A Java implementation of this algorithm is provided as SepaPnkIterator
. It is part of jcombinatorics
, the Java Combinatorics Library up on GitHub and released under the MIT license.
Ad-hoc performance testing was conducted on a 2.4 GHz Intel Core 2 Duo with 2GB RAM running OS X 10.5.8 and Apple’s Java 1.6.0_15. Results revealed that Johnson’s SEPA can generate all 479,001,600 permutations of P(12) at over to 38,000 permutations/ms. The above algorithm computes P(12,12) at around 32,000 permutations/ms which makes it nearly 85% as fast as SEPA P(n).
This article is also available for download as a PDF.
I’d love to hear from others if you have any thoughts to share on a formal proof of this algorithm, or of analysis of its running time. Meanwhile, Enjoy!
July 2, 2010 at 9:21 pm
Does your P(n,k) work for arrays with repeated elements? For example if we have “aaaaab” and you have k = 3; you would need “aaa, aab, aba, baa”.
July 2, 2010 at 10:00 pm
Yes. The above pseudo-code can be extended to arrays with repeating elements (as long they’re totally ordered). In fact, check out TypedSepaPnkIterator (and its associated unit test) in jcombinatorics. It illustrates exactly what you’re asking for.
July 7, 2013 at 9:35 am
This was very helpful (especially the sequentially-worked example!) in helping me write this Web page:
http://www.andrewduncan.ws/combinatorics/permutations
I gave full credit; hope this is OK. Let me know.
July 19, 2013 at 8:04 pm
Hey, thanks for the acknowledgement and am just glad someone else managed to find this useful!
March 26, 2014 at 3:18 pm
Hi Alistair, your algorithm is very helpful. A c implementation can be found here https://github.com/randy3k/itercombin/blob/master/src/util/k-permutation.c
I am using your algorithm to develop a R package for combination and permutation iterators. The package is still under development but I will credit your contribution when it is released.
March 27, 2014 at 9:14 am
Hey, thanks, too. Glad to know another person’s found my brain dump useful and good luck!
April 7, 2014 at 4:21 pm
hyperlink changed: https://github.com/randy3k/iterpc/blob/master/src/utils/k-permutation.c