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.

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 (kn-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, a1ak-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!

About these ads

7 Responses to “A Simple, Efficient P(n,k) Algorithm”

  1. Abhiram Natarajan Says:

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


  2. 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.

  3. Randy Lai Says:

    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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: