Calculating Permutation without Recursion - Part 2

• Download source - 73.7 KB

Introduction

There are several algorithms about generating permutation which usually use recursion to produce the result. Instead in this tip, a non-recursion approach is presented.

Background

If you have read my previous tip, we showed how to use dynamic programming to generate permutation.

In that article, the results from the previous step would be applied to generate new result and old result would be removed.The problem that occurs is that old result would stay in memory to be collected later by garbage collector.

What's more, in each iteration, the Clear method of List is called to remove previous references which is time consuming and imagine for n! how much it affects the performance.

In this tip, we try to use memory efficiently and remove the above concerns.

Using the Code

In the beginning, I show you how the algorithm works and based on the algorithm, I have written a Console application which will be explained below.

The algorithm uses rotation to produce new permutation and it somehow works similarly to Heap's algorithm:

In our algorithm, we have a list to keep the result.

We insert the set into the list and based on the last item in the set, we create sub groups containing two adjacent members to n adjacent members and rotate each group to generate new results.

After generating new result, we insert them into the list and continue to process the next subgroup.

Consider the following example:

{A,B,C}

We insert {A,B,C} into our list.

Based on the last item ,'C', we select a two-member group 'B,C' and by rotating it, we have 'C,B' which generates ACB.

We cannot continue anymore by two-member group because the only group based on 'C' was 'BC': C,A are not adjacents and B,A are not based on the last item.

The {A,C,B} is inserted to the list. So now we have two items in our list {A,B,C} and {A,C,B}.

Next subgroup is triple and we have two items:

{A,B,C}=> rotating : {C,A,B},{B,C,A} ==> two items will be inserted to the list

{A,C,B]=>rotating: {B,A,C},{C,B,A} ==> two items will be inserted to the list

We have three-member sets which means we can proceed to maximum triple group.

Finally, we have six items in our list.

public char[][] Calculate(char[] items)
    {
        int length = items.Length;
        char[][] result = new char[Factorial(length)][];

        int iteration = length - 1;
        int index = 0;
        //first item is inserted here
        result[index++] = items;
        while (iteration > 0)
        {
            //we keep count of current result
            int resultCount = index;
            for (int i = 0; i < resultCount; i++)
            {
                int rotateLength = length - iteration;
                var curItem = result[i];
                if (rotateLength > 0)
                {
                    while (rotateLength > 0)
                    {
                        RotateRight(curItem, iteration - 1);
                        //the rotated item now is new item we copy it into new item
                        char[] newItem = new char[length];
                        curItem.CopyTo(newItem, 0);
                        result[index++] = newItem;
                        rotateLength--;
                    }
                    //This rotation causes that original item doesn't change
                    RotateRight(curItem, iteration - 1);
                }
            }

            iteration--;
        }

        return result;
    }

According to Calculate method, a jagged array is created based on the number of needed items. In the method, we neither resize the array nor add a new array so we are sure we are using memory efficiently.

The main part of code is done by RotateRight method:

public void RotateRight(char[] items, int startIndex)
      {
          int last = items.Length - 1;
          var temp = items[last];
          int len = items.Length;
          Array.Copy(items, startIndex, items, startIndex + 1, len - (startIndex + 1));
          items[startIndex] = temp;
      }

This method takes an array to rotate and also startIndex of the array which rotation should start from.

Thus easily by specifying startIndex, we can rotate only any sub group of the set.

More Optimization

In the above code, it's seen that we allocate amount of memory which we need:

char[][] result = new char[Factorial(length)][];

And each time we generate new item, a memory for that item is created and imagine how many times this process is repeated if we have 11 items? Almost 40 million times!

What if we are able to allocate whole needed memory at once?

If we are, we can get rid of that repetitive task and also we avoid memory fragmentation.

To achieve this goal, I will replace the jagged array with a one dimensional array.Therefore accessing array and managing index will be done by some calculations and I should take care of them.

public char[] Calculate(char[] items)
       {
           int length = items.Length;
           char[] result = new char[Factorial(length) * length];

           int iteration = length - 1;
           int index = 1;
           //first item is inserted here
           Array.Copy(items, result, length);
           while (iteration > 0)
           {
               //we keep count of current result
               int resultCount = index;
               for (int i = 0; i < resultCount; i++)
               {
                   int rotateLength = length - iteration;
                   if (rotateLength > 0)
                   {
                       int startIndex = i * length + (iteration - 1);
                       int lastIndex = (i + 1) * length - 1;
                       while (rotateLength > 0)
                       {
                           RotateRight(result, startIndex, lastIndex);
                           //the rotated item  is new item and we copy it into new item
                           Array.Copy(result, i * length, result, index * length, length);
                           index++;
                           rotateLength--;
                       }
                       //This rotation causes that original item doesn't change
                       RotateRight(result, startIndex, lastIndex);
                   }
               }

               iteration--;
           }

           return result;
       }
       public void RotateRight(char[] items, int startIndex, int lastIndex)
       {
           var temp = items[lastIndex];
           int len = lastIndex + 1;
           Array.Copy(items, startIndex, items, startIndex + 1, len - (startIndex + 1));
           items[startIndex] = temp;

       }

Following depicts the performance difference between two above algorithms with 11 characters on an Intel Core I3 processor:

First version:

And the result with optimized version:

This algorithm also has the capability to be implemented in multi-threading and you can decrease the time to less than 1 second !!!

Points of Interest

As stated earlier, we tried to use memory efficiently for this algorithm and we were successful to allocate just needed memory and avoid allocating unnecessary memories.

We also noticed how expensive memory allocation is and by changing a jagged array to a one dimensional array how much it affected the performance.

This algorithm doesn't take into account the ordering either and I will present you another algorithm in my next article which considers ordering.

History

• Version 1.0: 07/04/2015