Last time on FAIC I described an algorithm for producing every permutation of size n such that any two successive permutations differ only by swapping two adjacent items. Today let’s actually write some code to implement this algorithm.

The first thing I’m going to need is a helper function that can insert an element into a sequence. That’s easy enough:

public static class Extensions
{
    public static IEnumerable<T> InsertAt<T>(
      this IEnumerable<T> items, int position, T newItem)
    {
        if (items == null)
            throw new ArgumentNullException("items");
        if (position < 0)
            throw new ArgumentOutOfRangeException("position");
        return InsertAtIterator<T>(items, position, newItem);
    }

    private static IEnumerable<T> InsertAtIterator<T>(
        this IEnumerable<T> items, int position, T newItem)
    {
        int index = 0;
        bool yieldedNew = false;
        foreach (T item in items)
        {
            if (index == position)
            {
                yield return newItem;
                yieldedNew = true;
            }
            yield return item;
            index += 1;
        }
        if (index == position)
        {
            yield return newItem;
            yieldedNew = true;
        }
        if (!yieldedNew)
            throw new ArgumentOutOfRangeException("position");
    }
}

Something to notice here is that my error checking is not in an iterator block. (An iterator block is the technical name for a method that contains a yield return or yield break.) When you call a method that contains an iterator block it immediately returns an object representing the sequence; the error checking does not happen until the caller actually attempts to enumerate the first element in the sequence. Therefore I follow standard practice here of making the public method do the error checking eagerly, and the private method actually makes the sequence object. As you’ll see, I do this trick again below.

Now I’m going to need a class to represent a permutation. It should be immutable of course. Logically it is a value, and I’m going to implement it by making a little n-item array of ints that stores the numbers 0 through n-1. So the size of the permutation will be the same size as a reference to an array. It’s small, it’s logically a value, so let’s make it a struct.

struct Permutation : IEnumerable<int>
{
    public static Permutation Empty { get { return empty; } }
    private static Permutation empty = new Permutation(new int[] { });
    private int[] permutation;
    private Permutation(int[] permutation)
    {
        this.permutation = permutation;
    }
    private Permutation(IEnumerable<int> permutation) 
        : this(permutation.ToArray()) { }
    public static IEnumerable<Permutation> HamiltonianPermutations(int n)
    {
       ... 
    }
    public int this[int index]
    {
        get { return permutation[index]; }
    }
    public IEnumerator<int> GetEnumerator()
    {
        foreach (int item in permutation)
            yield return item;
    }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
    public int Count { get { return this.permutation.Length; } }
    public override string ToString()
    {
        return string.Join<int>(",", permutation);
    }
}

OK, we’ve got a nice little immutable struct. The challenge is to fill in the body of HamiltonianPermutations(int n).

As always when writing a recursive algorithm we come back to the basic pattern: If the job is trivial then return the result. Otherwise, break the problem down into smaller problems, solve them recursively, and combine the results. Again, we’ll start by doing some eager error checking:

public static IEnumerable<Permutation> HamiltonianPermutations(int n)
{
    if (n < 0) 
        throw new ArgumentOutOfRangeException("n");
    return HamiltonianPermutationsIterator(n);
}

Remember the recursive action of the method is: take each smaller permutation, and insert the number n-1 into each of those permutations at each of n possible positions, alternating whether we insert at positions 0, 1, 2, … n, or positions n, … , 0:

private static IEnumerable<Permutation> HamiltonianPermutationsIterator(int n)
{
    if (n == 0)
    {
        yield return Empty;
        yield break;
    }
    bool forwards = false;
    foreach (Permutation permutation in HamiltonianPermutationsIterator(n - 1))
    {
        for (int index = 0; index < n; index += 1)
        {
            yield return new Permutation(
                permutation.InsertAt(forwards ? index : n - index - 1, n - 1));
        }
        forwards = !forwards;
    }
}

That looks pretty straightforward. And indeed, if we then run

foreach (Permutation p in Permutation.HamiltonianPermutations(5))
    Console.WriteLine(p);

We get

0,1,2,3,4
0,1,2,4,3
0,1,4,2,3
0,4,1,2,3
4,0,1,2,3
4,0,1,3,2
0,4,1,3,2
... a whole bunch more permutations ...
4,1,0,3,2
4,1,0,2,3
1,4,0,2,3
1,0,4,2,3
1,0,2,4,3
1,0,2,3,4

Which lists every permutation exactly once and as a bonus gives a Hamiltonian tour of the vertices of the permutohedron.

Extra super bonus: My colleague Bob – who is from the UK, where these things happen – points out to me that this algorithm is well-known to aficionados of change ringing, whereby a subset of all the possible permutations of ringing a series of bells is produced and then actually executed on enormous bells. Fascinating!

And I should probably mention that the algorithm I’ve presented is known to combinatorics people as the Steinhaus–Johnson–Trotter algorithm.

Next time on FAIC: Here we have obtained all the permutations, in a particular order. Since they are in order, we can assign a number to each. Can we produce the mth permutation of size n without calculating all the other permutations before it? We’ll give it a shot!