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):

Read the rest of this entry »


(I originally planned this to be a single article, but because of the scope decided to split it into two parts. Read the first part for the the basics of using Sun’s HttpServer to conduct functional HTTP testing. Here we revisit our functional test and rewrite it using JUnit 4.7’s new Interceptors feature.)


In my previous post, I demonstrated how to use Sun’s HttpServer API to write a functional test of an HTTP ‘conversation’.

Recall that I thought my initial solution seemed inelegant. It was verbose, with some start up and shutdown code that would have to be repeated for each test, and which I felt cluttered the actual test code.

It was also tedious, in the sense that the raw HttpHandler and HttpExchange API required us to do quite a few things manually, and unintuitively (such as having to compute and write out the length of our response before the response itself).

In this post, we’ll explore how to use the new Interceptors feature ‘quietly’ released with JUnit 4.7 to write reusable, portable pre and post-test behaviour. I’ll also exhibit a convenient HttpHandler implementation that simplifies some of the effort required in responding to HTTP requests.

Read the rest of this entry »

(I originally planned this to be a single article, but because of the scope decided to split it into two parts. This first part explores the basics of using Sun’s HttpServer to conduct functional HTTP testing. Part 2 revisits the following test using JUnit 4.7’s new interceptors (rules) feature and demonstrates a simpler HTTP handler.)


At work, we recently had the need to perform functional testing of a custom client that used HTTP as a transport. This isn’t strictly unit testing since we’re conducting actual HTTP over a socket & port instead of stubbing out or mocking the server, but in this case that was the only real way to test the client.

I could’ve fired up a standalone Web server and used that, but decided against it for a couple of reasons.

First, I wanted to have the server respond in a specific way to a particular client request. For example, if the request was for GET /1234.xml I might want to respond with an HTTP 200 and an XML response body. Another request for GET /0.xml might return an HTTP 404 instead.

To do that using, say, a Servlet container would mean writing multiple Servlets (mapped to various request URI) or a ‘rich’ Servlet with additional complexity. I didn’t want to have to write tests to test my test scaffolding!

Secondly, a standalone server would have to be started and stopped outside of our standard compile/test/package process (using Maven). Other people wouldn’t be able to run the tests successfully without having the test server up as well.

Clearly, the best way to go was to use an embedded HTTP server, which would allow us to provide specific responses tailored for each unit test.

As luck would have it, it turns out that Sun’s Java 6 implementation comes with a lightweight HTTP server API built in. Read on as I demonstrate the basic use of Sun’s HTTP server classes to write a functional test.

Read the rest of this entry »

I’ve been trying to get my feet wet writing code for the Eclipse platform. I figured a good first step is to become familiar with Eclipse SWT—the Standard Widget Toolkit, and work my way up from there.

Since I use Maven, I had to struggle a bit finding out how to configure my Maven project properly so that it’ll build an SWT app that’ll run both under Eclipse and from the terminal.

A little Googling brought me to Brice Lambi’s post on Maven SWT builds, but that was a little outdated.

In particular (and only after careful reading), the guide to Deploying SWT apps on Mac OS X says that the -Djava.library.path=.. option is needed for Eclipse 3.2.2 and earlier. Apparently, starting with 3.4 all you need is your OS-specific JAR (see here).

Anyway, after much fiddling about, I was able to get it all working like so: Read the rest of this entry »

David Saff wrote in on Introducing MagicTest, asking why not just instantiate the variable in-line (private Foo foo = new Foo();).

Which brings me to the real reason for coming up with MagicTestActiveTest.

A code sample is worth a thousand words. Suppose we have a Spring JPA data access object:

public class WidgetDao extends JpaDaoSupport {

  public WidgetDao(final EntityManager entityManager) {

  public Widget find(long id) {
    return getJpaTemplate().find(Widget.class, id);


WidgetDao needs a JPA EntityManager provided to it at construction time. Normally, to write a unit test for WidgetDao we’d have to create our mock objects and setup our test scaffolding manually.

Using ActiveTest, however, all we need to write is:

public class WidgetDaoTest extends ActiveTest<WidgetDao> {

  private WidgetDao widgetDao;

  private EntityManager em;

  public void testFind() {
    Mockito.verify(em).find(Widget.class, 42);


I’m lazy like that.
Read the rest of this entry »

Introducing MagicTest

May 28, 2009

If you’ve written enough JUnit 4 tests, then you should be familiar with code that looks like:

public class FooTest {

  private Foo foo;

  public void setUp() {
    foo = new Foo();

  public void testBar() {

Now, how often have you wished it were possible to simply go straight to @Test, do not pass setUp(), do not have to new Foo()?

Introducing MagicTest

So I came up with MagicTest, a parameterized base class for JUnit 4 tests that’ll let us do just that. Read the rest of this entry »

The following code is provided for educational/illustrative purposes only.

This is probably just a clever hack. This is not kosher. To all students of the Java language, please do not start using this in your day-to-day code. Let me be the first to admit that I haven’t used this extensively and I wouldn’t recommend using it for production.

Disclaimers aside, I won’t give any more background into Java generics. For those in need of an introduction, Angelika Langer’s Java Generics FAQ explains a lot of things with more clarity and depth than I ever could.

The basic problem is, given a generic class, we would like to determine the type parameter to that class at run-time..

I’ve found myself needing to do this more than once. The simplest example I can contrive is one when we want the Base class to perform run-time type-checking of some input parameter. Read the rest of this entry »