Home > Posts > Combinatorics library (Silverlight for Windows Phone)

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:

  1. make the IMetaCollection interface public so that I could abstract the use of any combinatorics operation based on user selection
  2. add CombinatoricsOp class to help with using any combinatorics operation via one entry point
  3. 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(); } }   }   }

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

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

%d bloggers like this: