C# – Rx and Permutation

Today I read an introduce to a guessing game which hosted on http://jotto.ciphertechs.com/. In this game the machine will generate a random 5-letters word and we try to guess the word through hints given that how many letters did we guess correctly. Who has less tries to guess a word is the better. Guessing the letters in that word is not difficult because each letter is unique. In my turn after some tries I found out 5 letters of that word which are ‘a’, ‘r’, ‘c’, ‘l’ and ‘e’. Now it’s more difficult because I must find out how these letters are arranged to make a meaningful word.

This leads to a task of calculating all permutations of 5 letters forming a word and then choose a meaninful one from this word list. It’s pretty simple to calculate permutation with C# and I think you can find out a ton of examples in internet out there. Therefore the topic of this blog does not discuss about how I calculate the permutation but I would like to introduce an extension which help me to solve this problem pretty fast. That is Reactive Extensions http://msdn.microsoft.com/en-us/devlabs/ee794896.

Rx is a library for composing asynchronous and event-based programs using observable collections.“. My colleague introduces me this extension. It’s very powerful but I am new to it. Therefore in this post I will not metion anything about asynchronous or event-based programs but I would like to illustrate a very small example using Interactive library of Rx to calculate permutation for my game. There’s are installation packages of Rx on the homepage but we can download its packages through Visual Studio.

1. Go to http://nuget.codeplex.com/releases and click on NuGet Package Manager to download Nuget. Click “I Agree”.
2. Open the “Download File” with “Microsoft Visual Studio Version Selector”

Open with Firefox

3. Click to “Install” Nuget add-on

Install Nuget

4. In Visual Studio, create a project to calculate the permutations of the 5 letters above. Then choose Tools –> Library Package Manager –> Add Library Package Reference… (Be sure that in Solution Explorere you are selecting a project. Otherwise there’s an error message telling that “Project” is not supported”.

Library Package Reference

5. Choose “Online” option, then enter “rx” on search box and choose to install Rx-Main and Rx-Interactiv

Rx Package install

6. After installing this package, new references will be inserted to your project such as System.Reactive, System.Observable and System.Interactive. In project folder there are also new folder “packages” which contains all neccessary files of Rx. It’s comfortable to use a package in a project because it will be automatically updated when new version comes. However it makes our project bigger and the library is not “really” for sharing to other projects because it’s put under a defined project folder.
Now insert a static class to add extended Permutation method to IEnumerable

public static class EnumerableExtension
{
	public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source)
	{
		if (!source.Any())
			return EnumerableEx.Return(Enumerable.Empty<T>());
		else
			return from item in Permutations(source.Skip(1))
				   from i in Enumerable.Range(0, item.Count() + 1)
				   select item.Take(i).Concat(EnumerableEx.Return(source.First())).Concat(item.Skip(i));
	}
}

7. Enter some code for handling button “Calculate”. You can see that I give 5 letters as input and call Permuations function on “source” object to generate all possible cases. With help of Linq I put these permutations in a beautiful string to display on textbox.

private void btnCalculate_Click(object sender, RoutedEventArgs e)
{            
	IEnumerable<string> source = new List<string>{"a","r","c","l","e"};
	txtResult.Text = source.Permutations().Select(x => x.Aggregate((y, z) => y = y + z)).ToList().Aggregate((y, z) => y = y + " " + z);

}

8. And we have result of permutations for 5 letters about 120 cases.

Permutation

I found out the correct word is “clear” and you can find the complete source code at “Rx Permutation”

UPDATE 21.03.2012
If you don’t want to use Nuget to install Rx Extensions, you can download it directly with this link http://www.microsoft.com/download/en/details.aspx?id=28568 and install it as usual. After installing, you’ll have dlls in your reference list.

Rx Extensions

Leave a Reply

Your email address will not be published. Required fields are marked *