Combinatorics library (Silverlight for Windows Phone)
I recently found a very nice article at CodeProject on Combinatorics algorithms implementation (specifically Permutations, Combinations and Variations with Repetition option) using C# Generics:
http://www.codeproject.com/KB/recipes/Combinatorics.aspx
It uses a lexicographic algorithm, so it allows one to ask for “next” permutation/combination/variation from the collection of all possible ones, in the spirit of C++ Standard Library’s (STL) “next_permutation” algorithm.
My Anagram app for Windows Phone 7 is using this code (packed it in a Silverlight library)
I packed the files in a Silverlight for Windows Phone class library (named Combinatorics) and modification I had to do was to:
- make the IMetaCollection interface public so that I could abstract the use of any combinatorics operation based on user selection
- add CombinatoricsOp class to help with using any combinatorics operation via one entry point
- As a bonus there is also a Combinatorics.cd there (class diagram)
You can download the library to use with your WP7 Silverlight apps (Portable [PCL] version also available now) from http://github.com/zoomicon/Combinatorics
Please give due credit to original author of Combinatorics code (and myself if you use my additions too).
The code for CombinatoricsOp class I added is below. Just call GetCombinatoricsOp to get a Permutations, Combinations or Variations class instance (all implement IMetaCollection interface) and then use the enumerator (with extra method to get count of items without counting them one-by-one) as described in the CodeProject article mentioned above.
//Version: 20111119 //Author: George Birbilis (birbilis@kagi.com) using System; using System.Collections.Generic; namespace Facet.Combinatorics { public static class CombinatoricsOp { public enum CombinatoricsOpType { Permutations = 0, PermutationsWithRepetition = 1, //--- Combinations = 2, CombinationsWithRepetition = 3, //--- Variations = 4, VariationsWithRepetition = 5 } public static IMetaCollection<string> GetCombinatoricsOp( IList<string> values, CombinatoricsOpType opType, int take){ switch (opType) { case CombinatoricsOpType.Permutations: return new Permutations<string>(values);
case CombinatoricsOpType.PermutationsWithRepetition: return new Permutations<string>(values,GenerateOption.WithRepetition); case CombinatoricsOpType.Combinations: return new Combinations<string>(values, take); case CombinatoricsOpType.CombinationsWithRepetition: return new Combinations<string>(
values, take, GenerateOption.WithRepetition); case CombinatoricsOpType.Variations: return new Variations<string>(values, take); case CombinatoricsOpType.VariationsWithRepetition: return new Variations<string>(
values, take, GenerateOption.WithRepetition); default: throw new NotImplementedException(); } } } }