Partly encouraged by this year’s Google Code Jam contest, but likely more so by the lack of any combinatorics functionality in the .NET Framework (still missing in most recent version 4.0), I thought I would put a bit of effort into writing efficient implementations of algorithms in C#. The following algorithms are implemented (between the GetPermutations and GetCombinations methods).
- Permutations with repetition
- Permutations without repetition
- Combinations with repetition
- Combinations without repetition
Worth noting is that the algorithms run purely in-place on the list, and involve no recursion (only a single while loop). While memory usage is minimal, they do of course still run in factorial (or equivalently exponential) time complexity, though it’s well known you can’t do any better than that if you require all permutations/combinations of a given size.
All four algorithms have been sufficiently tested and verified for small lists, running on .NET 4.0 (Windows). I would be inclined to bet everything runs perfectly well on Mono too. Needless to say, bug reports and feedback are welcome.