Permutations

Download the source code.

Given a string of input characters, how do we generate a list of every possible permutation of those characters? For example, given "cat" as a string, we should print out:

            cat
            cta
            act
            atc
            tca
            tac
        

It makes for a fun programming exercise. There are a lot of different ways to solve this, with varying tradeoffs of space, speed, and understandability. I decided to use it as an opportunity to explore the C# 2.0 feature of iterator blocks, which provide a quick way to support foreach syntax without writing a lot of manual code to manage the iteration state. I also took it as an opportunity to explore generics, since I might want to generate permutations for any iterable data type.

My implementation allows calling code to choose between an implementation using the iterator block and a more traditional implementation that manually manages a stack to keep track of the iteration state. For me, I think the jury is still out on the value of the iterator block feature. While it's true that the iterator block implementation requires much less code, I found it somewhat difficult and unintuitive to write that small portion of code.

I also got curious about performance, because I really had no way of knowing how Microsoft chose to implement the iterator block under the covers. I downloaded the CLR Profiler and measured some test runs with data sets of various sizes and types. In all cases, the manual stack-based implementation outperformed the iterator block in terms of speed. In most cases, the manual stack-based implementation also allocated much less memory than the iterator block. The one exception to this trend occurred during a test run with a List of int elements. At some point, I should revisit this and try to determine if my code is doing something sub-optimal while processing the List. Specific numbers from the CLR Profiler are stored in the CLRProfilerResults.txt file, included in the zip file.