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.
| Pi | a0 | a1 | a2 | a3 | a4 |
| ⋮ | ⋮ | ||||
| 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 | a0 | a1 | a2 | a3 | a4 |
| ⋮ | ⋮ | ||||
| 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):
Alistair Israel 