A Simple, Efficient P(n,k) Algorithm

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.

Table 1: P(5)17..24 with rightmost ascents highlighted.
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.

Table 2: P'(5)17..24 after swaps (in red). Highlighted cells are about to be reversed.
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):

Table 3: P(5, 3)0…5
Pi a0 a1 a2
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), a0, a1 and a2, we actually find P(5, 3). Except, to get P(5, 3) from P(5) we need to ‘skip’ a few permutations.

Table 4: P(5) with P(5, 3) highlighted
P(5)i a0 a1 a2 a3 a4
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 kth or 3rd position, a2 as the ‘edge’.

Table 5: P(5) where a0, a1 and a2 change. The 3rd position, or a2 is the ‘edge’
Pi a0 a1 a2 a3 a4
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.

Table 6: P(5) → P(5, 3), showing the edge about to be swapped with the next higher number
Pi a0 a1 a2 a3 a4
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.

Table 7: P(5, 3), showing the edge about to be swapped, or, after reversal, the actual ascent and values to swap (as in SEPA)
Pi a0 a1 a2 a3 a4
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 aj > aedge
j = k
while j < n and aedge >= aj,
    ++j

if j < n {
    swap aedge, aj
} else {
    reverse ak to an-1

    // find rightmost ascent to left of edge
    i = edge - 1
    while i >= 0 and ai >= ai+1,
          --i

    if i < 0,
          // no more permutations
          return 0

    // find j in (n-1…i+1) where aj > ai
    j = n - 1
    while j > i and ai >= aj
          --j

    swap ai, aj
    reverse ai+1 to an-1
}

output a0, a1 … ak-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.

Table 8: P(5, 3). a2 is the ‘edge’. Red values are about to be swapped, yellow cells are about to be reversed.
Pi a0 a1 a2 a3 a4 Step
0 0 1 2 3 4 swap a2, a3
1 0 1 3 2 4 swap a2, a4
2 0 1 4 2 3 reverse a3..4
0 1 4 3 2 swap a1, a4
0 2 4 3 1 reverse a2..4
3 0 2 1 3 4 swap a2, a3
4 0 2 3 1 4 swap a2, a4
5 0 2 4 1 3 reverse a3..4
0 2 4 3 1 swap a1, a3
0 3 4 2 1 reverse a2..4
6 0 3 1 2 4 swap a2, a3
7 0 3 2 1 4 swap a2, a4
8 0 3 4 1 2 reverse a3..4
0 3 4 2 1 swap a1, a2
0 4 3 2 1 reverse a2..4
9 0 4 1 2 3 swap a2, a3
10 0 4 2 1 3 swap a2, a4
11 0 4 3 1 2 reverse a3..4
0 4 3 2 1 swap a0, a4
1 4 3 2 0 reverse a1..4
12 1 0 2 3 4 swap a2, a3
⋮ ⋮ ⋮

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!

11 thoughts on “A Simple, Efficient P(n,k) Algorithm”

  1. 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”.

    Reply

      1. Hi Alistair,

        I am just informed that there is a typo in your algorithm.

        this line

        while i > 0 and ai >= ai+1,

        should be

        while i >= 0 and ai >= ai+1,

        if not, i will never be negative.

  4. Hi, I wanted to say to you to thank you for the pseudo-code. I was able to implement the partial permutations generator as a command for the G’MIC scripting language – https://github.com/GreycLab/gmic-community/commit/8dd5d50cd5d0526a36263358d736b9c636ffd3e6 .

    I know you don’t understand the language that much, but you can at least tell that the if ( axis() , … ); output[0,s]; block used the algorithm you provided.

    Thank you anyways. I wouldn’t have made this without this page.

    Reply

Leave a comment