So as promised I finally got around to putting up the code I spoke about in my last post, unfortunately after an initial attempt to post it here and a noticeable FAIL I decided to post it up to a new Google Code project called monoalgorithm, so now I have a project I can share and build up a collection of algorithms in :)

Anyway, it's under a new style BSD license and compiles and runs under Mono 1.9.1 so feel free to have a look and modify if you want. Of course now I have to learn how to use subversion as well as learning C++, Python etc... Obviously I must really like pain.

http://code.google.com/p/monoalgorithm/source/browse/trunk/Algorithm.cs

Bugger!

I never realised the finished formatting for a simple bit of HTML would look so bad in Blogger! I'll try and do something about that when I publish the full code tomorrow and in future posts.

Back over to .Net for a bit

Never completely happy with sticking to one language for any longer than a month (I get way to distracted) I've been playing around with C# over the last couple of weeks, specifically generics and lambda expressions with use in algorithms. The reason for this is as per usual something I came across on Project Euler, as I've done with all other problems I implemented the solution in Python - and I'm not likely to change that any time soon - but the initial solution came from C++ and the standard template library.

The problem involved determining lexicographical permutations which is a fairly common task when you want to test code. The reason for this is if you want to test a method with a range of values you can produce permutations of an original list and pass in each one, lexicographical simply means they are in order. For example, the list [0, 1, 2] can be arranged in the following permutations:

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

Initially I struggled to come up with a solution to this spending ages trying to figure out how to determine the next permutation in order. The answer came from the elegantly titled "Algorithm L". To summarise what it does I'll try and show an example in action, so first we start with our initial permutation.

1 2 3 4 5

First we start from the second to last index (in this case index 3 because indexes are zero based and the number there is 4) and work our way backwards until we find an index where it's value is less than the one after it which in this case is the same index we started at.

Index	0	1	2	3	4
Value	1	2	3	4	5
				^

So we assign this index as j (j = 3), next we start from the last index and work backwards to j until we find an index whose value is larger than the one at j, in this case it's nice and easy because it's the last index, and we set that index as m. If we had not found a value for j then there would be no further permutations.

Index	0	1	2	3	4
Value	1	2	3	4	5
					^

After we have found j and m we swap the two values at the indexes and then sort all the values after j, so in this instance we end up with:

1 2 3 5 4

If we repeated the process again from this permutation we would do something like this:

Index	0	1	2	3	4
Value	1	2	3	5	4
			j		m

Index	0	1	2	3	4
Value	1	2	4	5	3

Index	0	1	2	3	4
Value	1	2	4	3	5

Implementing this in Python was easy but I wanted to play with Generics in C# so I decided to implement it in that language.

Generics are a way in which we can write a class to work on different data types without implementing the code with 1 certain type, for instance if we create a method that sorted arrays we could write something like:

public void Sort(int[] arrayOfValues) { ... }

Which would work great but if we then wanted to sort an array of doubles or characters we would have to re-implement the method for different types so we end up with SortInt(), SortDouble() and so forth. Whilst this may be okay for a couple of types if we wanted to sort other types and custom types then re-writing this code becomes a lot of work, makes maintenance harder and introduces a greater chance of error. This is where generics comes in, instead of the method signature used above we can instead write it as follows:

public void Sort(T[] arrayOfValues) { ... }

When we call this method we then define the type of data we are working like so:

int[] myIntArray = new int[] { 1, 2, 3, 4 };
char[] myCharArray = new char[] { 'a', 'b', 'c', 'd' };

Sort(myIntArray);
Sort(myCharArray);

As you can see the method call is identical except that we are specifying the data type we intend to work with, the magic part here is the <T> after the method name, this indicates that we are using a generic type called T and we can use it in the method like we would a normal type.

public void PrintValues(T[] arrayOfValues)
{
   foreach (T value in arrayOfValues)
   {
       Console.WriteLine(value);
   }
}

Now one problem we will encounter with the Sort() method we described above is that we cannot compare generic types as we can't guarantee that they will be comparable, to get around this we add a constraint to the method like so:

public void Sort(T[] arrayOfValues) where T: IComparable { ... }

This instructs the system to only accept types which implement IComparable, with this guarantee in place we can now compare values in the method:

public void Sort(T[] arrayOfValues) where T: IComparable
{
   ...
       if (arrayOfValues[a].CompareTo(arrayOfValues[b]) > 0)
       {
           T holder = arrayOfValues[a];
           arrayOfValues[a] = arrayOfValues[b];
           arrayOfValues[b] = holder;
       }
   ...
}

Using this we can implement our next_permutation algorithm in C# and enable it to work with any types (restricted to comparable types of course) we choose. Unfortunately I don't have the code to hand at the moment so I'll post it up for all to see and criticise (be kind please) tomorrow.

This has taken up quite a lot of space for now so I'll save the post on Linq for another day, but not to long away I promise as I want to post about it before I go for the next big C++ push.