IanG on Tap

Jason Whittington isn't the only person who can do bizarre and pointless stuff with C# iterators. :-)

On a mailing list I frequent, Tim Tabor asked:

"What handy tool will enumerate all permutations, of, say, a list of 10 doubles taken five at a time?"

Hugh Brown posted an example solution using Python generators. So I thought I'd take a crack at it in C#. The new iterator functionality coming in V2.0 looks quite similar to Python's generators, so I thought I'd see how it compared.

As you can see, the bulk of his Python implementation fits in 5 lines of code. (6 if you include the function declaration, 7 if you include the documentation line.) The main body of mine is 20 lines, but a large part of that is because I'm using a much less frugal layout style - the majority of those lines are either blank, or just contain a brace, or are present because I've split one statement across multiple lines. If I format the code so that it is laid out in as similar a way to the Python example as possible it only requires 8 lines of code. (The curly braces end up in funny places though... Python is able to be much more compact because it relies entirely on indentation to indicate nesting of code blocks, so you don't waste space on braces.) And I can get it all the way down to 5 if I make it slightly less flexible, by requiring an IList<T> - because it currently accepts any IEnumerable<T>, it's slightly more complex than the Python example, mainly because we can't assume that the input will support random access.

So only 3 extra lines of non-brace code are required. Well, kind of. I also had to write a couple of utility methods. Python has intrinsic language support for various list operations. C# doesn't, so I ended up writing a generic concat operation, and also a method to remove an item from a list. This makes the total listing much longer than the Python version, but these are generically useful utility functions that you could move elsewhere and reuse.

using System;
using System.Collections.Generic;

public class PermuteUtils
{
    // Returns an enumeration of enumerators, one for each permutation
    // of the input.
    public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> list, int count)
    {
        if (count == 0)
        {
            yield return new T[0];
        }
        else
        {
            int startingElementIndex = 0;
            foreach (T startingElement in list)
            {
                IEnumerable<T> remainingItems = AllExcept(list, startingElementIndex);

                foreach (IEnumerable<T> permutationOfRemainder in Permute(remainingItems, count - 1))
                {
                    yield return Concat<T>(
                        new T[] { startingElement },
                        permutationOfRemainder);
                }
                startingElementIndex += 1;
            }
        }
    }

    // Enumerates over contents of both lists.
    public static IEnumerable<T> Concat<T>(IEnumerable<T> a, IEnumerable<T> b)
    {
        foreach (T item in a) { yield return item; }
        foreach (T item in b) { yield return item; }
    }

    // Enumerates over all items in the input, skipping over the item
    // with the specified offset.
    public static IEnumerable<T> AllExcept<T>(IEnumerable<T> input, int indexToSkip)
    {
        int index = 0;
        foreach (T item in input)
        {
            if (index != indexToSkip) yield return item;
            index += 1;
        }
    }
}

The following code tries the code out on a list of ints and a list of strings.

class App
{
    static void Main(string[] args)
    {
        int[] intInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        ShowPermutations<int>(intInput, 2);

        string[] stringInput = { "Hello", "World", "Foo" };
        ShowPermutations<string>(stringInput, 3);

    }

    // Print out the permutations of the input 
    static void ShowPermutations<T>(IEnumerable<T> input, int count)
    {
        foreach (IEnumerable<T> permutation in PermuteUtils.Permute<T>(input, count))
        {
            foreach (T i in permutation)
            {
                Console.Write(" " + i);
            }
            Console.WriteLine();
        }
    }
}

The Python version is definitely more compact. Is it more readable? To be honest, I don't know - I'm a beginner at Python, so to me, it looks a lot less readable than C# for the simple reason that I've been using C# for several years. The intrinsic list mangling syntax takes a while for me to get my head around, but I expect it becomes second nature after a while. It's not like all of C#'s syntax is instantly obvious to the beginner. :-)