Permutations unlimited

Yesterday i stuck on the problem to generate all permutations of the numbers from 0 to 11. I used a common recursive approach and stored all results in a list – this results in an OutOfMemoryException! And my aim is to have access to all permutations from 0..100. So i decided to write a separate class for generating permutations of n numbers by implementing a step-by-step permutation-enumerator. This is the piece of code:

public class Permutations : IEnumerable<int[]>
{
    private int _n;
    public Permutations(int n)
    {
        _n = n;
    }

    #region IEnumerable<IEnumerable<int>> Members

    public IEnumerator<int[]> GetEnumerator()
    {
        return new PermutationEnumerator(_n);
    }

    #endregion

    #region IEnumerable Members

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    #endregion

    private class Pair<F, S>
    {
        public F First { set; get; }
        public S Second { set; get; }

        public Pair(F first, S second)
        {
            First = first;
            Second = second;
        }
    }

    private class PermutationEnumerator : IEnumerator<int[]>
    {
        private int _n;
        public PermutationEnumerator(int n)
        {
            if (n < 0) throw new ArgumentOutOfRangeException("Only non-negative numbers allowed.");

            _n = n;

            Reset();
        }

        #region IEnumerator<IEnumerable<int>> Members

        private int[] _current;
        public int[] Current
        {
            get { return _current; }
        }

        #endregion

        #region IDisposable Members

        public void Dispose()
        {
            _depthPositionMap.Clear();
            _depthPositionMap = null;
            _current = null;
        }

        #endregion

        #region IEnumerator Members

        object System.Collections.IEnumerator.Current
        {
            get { return Current; }
        }

        public bool MoveNext()
        {
            _current = null;

            while (_depthPositionMap.Count > 0 && !GenerateNextPermutation()) ;

            if (_current == null) return false;

            return true;
        }

        public void Reset()
        {
            _current = new int[_n];

            for (int i = 0; i < _n; i++)
            {
                _current[i] = i;
            }

            _depthPositionMap = new SortedList<int, Pair<int, int[]>>();

            _depthPositionMap.Add(0, new Pair<int, int[]>(0, _current));
        }

        #endregion

        private SortedList<int, Pair<int, int[]>> _depthPositionMap = null;

        private bool GenerateNextPermutation()
        {
            int depth = _depthPositionMap.Keys[_depthPositionMap.Count - 1];

            Pair<int, int[]> pair = _depthPositionMap[depth];

            if (depth == pair.Second.Length - 1)
            {
                _current = pair.Second;
                _depthPositionMap.Remove(depth);
                return true;
            }

            if (pair.First == pair.Second.Length)
            {
                _depthPositionMap.Remove(depth);
            }
            else
            {
                int[] elements = pair.Second.ToArray();

                int tmp = elements[pair.First];
                elements[pair.First] = elements[depth];
                elements[depth] = tmp;

                _depthPositionMap.Add(depth + 1, new Pair<int, int[]>(depth + 1, elements));

                pair.First++;
            }

            return false;
        }
    }
}

Now its only a small step to create a generic Permutation-class – and here it is:

public class Permutations<T> : Permutations, IEnumerable<IEnumerable<T>>
{
    T[] _elements;

    public Permutations(IEnumerable<T> collection)
        : base(collection.Count())
    {
        _elements = collection.ToArray();
    }

    #region IEnumerable<IEnumerable<T>> Members

    public new IEnumerator<IEnumerable<T>> GetEnumerator()
    {
        using (IEnumerator<int[]> enumerator = base.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                T[] result = new T[enumerator.Current.Length];
                for (int i = 0; i < enumerator.Current.Length; i++)
                {
                    result[enumerator.Current[i]] = _elements[i];
                }
                yield return result;
            }
        }
    }

    #endregion
}

Feel free to comment this approach…

Robot speaks C#

Some time ago i linked to a programming contest based on the well known boardgame RoboRally. Its also some time ago the results got presented on the page of freiesMagazin. I sent in a KI-player written in C#/Mono, which is disliked by a part of the free-software community – maybe for a good reason?! (Im not into this discussion – im programming in C#/.NET/Mono for a lot of other good reasons…) However, i could make my robot win the tournament! My robot and me are very proud of it cause there were a lot of good approaches and programs to resolve the task.

At the beginning my algorithm was just a straight forward Ford-Bellmann after transforming the board and the possible positions of the roboter into a stategraph. I tried to keep the probability in mind while implementing it but after a while i noticed that searching for the best path couldnt get me rid of the problem of not knowing which cards will be next and whether the roboter would be able to follow the path by these cards. But a good friend of mine, Georg Hofmann, gave me a good advice: Monte-Carlo-Simulation. And he also provided the idea of the actual algorithm (i suggest reading the rules of the contest before).

The aim: To get the expected value of needed rounds to reach the target for every field.
Starting values: 1 on every field, 0 for the target field.
Simulation: Draw 8 cards. Calculate for EVERY field (A), which fields can be reached by
these cards and choose the one with the actual lowest expectation value (B). Correct the
expectation value for A as follows: E(A) = 0.9 * E(A) + 0.1 * E(B)
Do the simulation as often as possible to get a good result...

(Of course you have to take care of fields that leads to the dead of the robot – they need some kind of penalty as well as they dont need to be simulated)
After running these little piece of algorithm (very(!) often) the roboter “knows” what to do: Always choose those 5 cards that leads to the field with the lowest expectation value – its statistically best!

I wrote a more detailed article (in german) about this approach in combination with an introduction into C#/Mono for freiesMagazin. The article will be available at the May 2010 edition of freiesMagazin. But this is not the end of the roboters… be prepared

Cursors in MSSQL – Copy/Paste template

    DECLARE @myName varchar(50)
    DECLARE @myDesc varchar(50)

    DECLARE myCursor CURSOR FOR 
        SELECT Name, Description
        FROM Table
        WHERE ID = @parameter

    OPEN myCursor 
    FETCH NEXT FROM myCursor INTO @myName, @myDesc

    WHILE @@FETCH_STATUS = 0
    BEGIN
        PRINT @myName + '; ' + @myDesc
        FETCH NEXT FROM myCursor INTO @myName, @myDesc
    END

    CLOSE myCursor
    DEALLOCATE myCursor

Reminder: Use unique cursor names! (if calling a procedure inside cursor which uses a cursor itself, the cursor names need to be unique)

Clipboard event handling

And another very nice site i found here: An very good example how to keep track of clipboardcontent. No time to go into deeper details… maybe later, just follow the link by now!

Reading binary data in C#

This caption is taken directly from an article i found here. The final result of this post is the following code:

/// <summary>
/// Reads data from a stream until the end is reached. The
/// data is returned as a byte array. An IOException is
/// thrown if any of the underlying IO calls fail.
/// </summary>
/// <param name="stream">The stream to read data from</param>
/// <param name="initialLength">The initial buffer length</param>
public static byte[] ReadFully (Stream stream, int initialLength)
{
    // If we've been passed an unhelpful initial length, just
    // use 32K.
    if (initialLength < 1)
    {
        initialLength = 32768;
    }
    
    byte[] buffer = new byte[initialLength];
    int read=0;
    
    int chunk;
    while ( (chunk = stream.Read(buffer, read, buffer.Length-read)) > 0)
    {
        read += chunk;
        
        // If we've reached the end of our buffer, check to see if there's
        // any more information
        if (read == buffer.Length)
        {
            int nextByte = stream.ReadByte();
            
            // End of stream? If so, we're done
            if (nextByte==-1)
            {
                return buffer;
            }
            
            // Nope. Resize the buffer, put in the byte we've just
            // read, and continue
            byte[] newBuffer = new byte[buffer.Length*2];
            Array.Copy(buffer, newBuffer, buffer.Length);
            newBuffer[read]=(byte)nextByte;
            buffer = newBuffer;
            read++;
        }
    }
    // Buffer is now too big. Shrink it.
    byte[] ret = new byte[read];
    Array.Copy(buffer, ret, read);
    return ret;
}

Charlie Winston – Buy before die

Not all european people might have heard this name before – but they should! His single first “Like a hobo” is more often played in the radio in the last days. And this time for a good reason: Its great! Not only the single – the whole CD “Hobo” is! And if u ask me: The song “Like a hobo” is not my favorite, but neverless its rocks like the whole album. It might be hard for you to listen more than the first 3 songs, cause u will repeat them endlessly!! So remember the name: Charlie Winston. Give it a try…

PS: I dont get paid for any commercial, im just enthusiastic

.Net 3.* Language Extensions

A good site with examples for the language extension feature of .Net 3.* can be found here. As a shortcut look at this example taken from linked site:

public static bool In(this object o, IEnumerable c)
{
  foreach(object i in c)
  {
    if(i.Equals(o)) return true;
  }
  return false;
}

What the fuck is WUBI?!

The answer is as easy as the program itself: Its an ubuntu installer for windows. If u are a windows user but sometimes u need a linux u could install yourself a virtual machine.

I used VirtualBox for a long time – it was great but it was slow! As i decided to switch to Windows 7 i also decided to try an alternativ and what i found was WUBI. And now im happy: Its easier to install than a virtual machine, no need for an extra partition and its fast! The only sad thing: Switching between Windows and Ubuntu needs a computer restart…

RoboRally – Roboter meets AI

A friend sent me an email with a link to a little programming contest. The aim is to program an AI for a roboter that should find a way from the origin to the destination – the rules are deeply inspired by the boardgame RoboRally. The reward may not be worth to invest time at all but to see a little robot moving around the holes and splippering over oil is great fun – u always hope that he might be clever enough to reach his aim and dont stuck… so, do it!

Binary Search Tree and Red-Black Tree in C#

Willing to implement some missing(?) base functionality in my own library to extend .NET i found these articles: Working with Red-Black Trees in C#, An Extensive Examination of Data Structures and Implementing a Red-Black Tree in C#.
While the first seems to be exactly what i was looking for, the second article on MSN provides some additional reading about datastructures. The sourcecode examples are somehow outdated cause they are written for .NET 2.0 but neverless its quite basic knowledge for everyone well explained. The last article reminds me at some point how i would have done it 10 years before I didnt read it at all, just got a quick look at the sources and my first thought was: Too much lines of code for a Red-Black Tree! But i should give it a second try – also the rest of the blog holds some extensive examples of different programming patterns. And you can never know enough about it…