Producing permutations, part three

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!

Advertisements

11 thoughts on “Producing permutations, part three

  1. Dear Eric,

    Outstanding post as always!

    I’m always amazed by how you put together a concise definition for the data structures! OK, you’re the C# guy, but it’s maybe the greatest benefit of reading your posts that contain code… 🙂 I learn a lot.

    For anyone interested: Eric’s A* series of posts exemplify my point even further…

    Hope we can have a lot more posts from your brilliant mind.

    God bless,
    Leniel

  2. Your private InsertAtIterator method does not need to be an extension method. Your public method which calls it does not invoke it with instance method syntax.

    Since you’re already tracking the index, the bool yieldedNew is unnecessary. The final check can be written:
    if (index < position) …
    The code is simpler and more concise after removing yieldedNew.

  3. Hi Eric,

    I recently discovered the ListSeparator property which is a little hidden in the Framework…maybe you know already. If not you might want to use sth like

    public override string ToString()
    {
    return string.Join(System.Globalization.CultureInfo.CurrentCulture.TextInfo.ListSeparator, permutation);
    }

    instead of

    public override string ToString()
    {
    return string.Join(“,”, permutation);
    }

    • Tom, I don’t think a localized list separator applies here, although not clearly stated in the documentation, I think the porpouse of the ToString() method is to generate a string in a culture invariant way, for localized versions the class should implement IFormattable.
      The misuse of ListSeparator may result in far worse problems than lack of globalization, for example, at least one version of Oracle SqlDeveloper had a bug in the database scriptor where the separator in INSERTs where replaced by the localized ones…

  4. Thanks for a fun and educating post as usual.

    Wouldn’t you save one Enumerator creation by just forwarding to the underlying Enumerator?

    public IEnumerator GetEnumerator()
    {
    return ((IEnumerable)permutation).GetEnumerator();
    }

  5. Some news involving a clever use of Hamiltonian paths reminded me of your posts. I thought I’d share: http://it.slashdot.org/story/15/06/05/175253/opening-fixed-code-garage-doors-with-a-toy-in-10-seconds

    Basically, this is brute forcing a garage opener. But instead of sending each combination in turn, it generates a single stream that includes all the possible combinations (at various shift positions). Apparently garage openers are implemented in a way that recognized the combination in the middle of a stream. This means the brute force is much faster…

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