Calculating Permutation Using Dynamic Programming

• Download source - 43.6 KB

Introduction

Recently, I was working on a problem to produce all permutations.

I used recursive approach to produce them but I was also thinking of using a non-recursive version. Finally, I came across the following algorithm that uses dynamic programming.

Of course, there are other algorithms which may be better and more efficient but I think my algorithm is simple to understand and can also be implemented in multi-threading.

Background

As you know, permutation is number of possibilities of combination of elements in a set. For example, for set {a,b,c},

we have 3! factorial possibilities:

{abc,} {acb}
{bac} {bca}
{cab} [cba}

and for a set with n elements, we have n! .

Using the Code

To use the code, first I will give you a big picture of how algorithm works.

For set {c}, we have just one permutation 'c' and for set {b,c} we can use previous result ,'c', and by adding 'b' to every possible position of 'c', we will have {b,c} and {c,b}.

So for {a,b,c}, we use the result from previous steps and we add 'a' to each position of previous results.

'a' + {b,c}==>position: beginning {a,b,c}
'a' + {b,c}==> position:middle {b,a,c}
'a' + {b,c]==>position:end {b,c,a}

The above procedure will also be applied for {c,b] which generates:

{a,c,b}, {c,a,b} ,{c,b,a}

This approach can be easily applied for different sets.

I have created a console application in Visual Studio 2013 which has a class named PermutationCalculator which is responsible for generating permutation and is called from Main method as below:

static void Main(string[] args)
      {
          string inputString = Console.ReadLine();
          PermutationCalculator permutationCalculator = new PermutationCalculator();
          var result = permutationCalculator.Calculator(inputString.ToCharArray());
          Console.WriteLine("Total items:" + result.Count);
          foreach (var item in result)
              Console.WriteLine(item);
          Console.ReadKey();
      }

The application accepts inputs from the user which is a string and will be passed as an array of chars to PermutationCalculator. In the Calculate function, because we already know how many items will be generated(n!), we specify the total item which is supposed to be returned. If you are not interested in allocating n! elements, I recommend you to read Lexicographic order part from Counting And Listing All Permutations by Alexander Bogomolny.

public class PermutationCalculator
{
    int Fact(int cnt)
    {
        int sum = 1;
        while (cnt > 0)
        {
            sum *= cnt;
            cnt--;
        }
        return sum;
    }
    public List<char[]> Calculate(char[] items)
    {
        if (items == null || items.Length == 0)
            return new List<char[]>();
        int length = items.Length;
        int currentPosition = length - 1;
        int totalItem = Fact(length);
        List<char[]> currentResult = new List<char[]>(totalItem);
        List<char[]> previousResult = new List<char[]>(totalItem);
        //Add last item to the previousResult list
        previousResult.Add(new char[] { items[currentPosition] });
        while (currentPosition > 0)
        {
            currentResult.Clear();
            foreach (var item in previousResult)
            {
                currentResult.AddRange(AddItem(item, items[currentPosition - 1]));
            }
            if (currentPosition - 1 > 0)
            {
                previousResult.Clear();
                previousResult.AddRange(currentResult);
            }
            currentPosition--;
        }
        return currentResult;
    }

    private List<char[]> AddItem(char [] currentItem, char newItem)
    {
        List<char[]> result = new List<char[]>(currentItem.Length+1);
        int pos = 0;
        while (pos <= currentItem.Length)
        {
            char[] item = new char[currentItem.Length + 1];
            int i = 0,j=0;

            while(j<currentItem.Length+1)
            {
                if (j == pos)
                {
                    item[j] = newItem;

                }
                else
                {
                    item[j] = currentItem[i++];
                }

                j++;
            }

            result.Add( item);
            pos++;
        }

        return result;
    }

    public List<char[]> CalculateParallel(char[] items)
    {
        if (items == null || items.Length == 0)
            return new List<char[]>();
        int length = items.Length;
        int currentPosition = length - 1;
        int totalItem = Fact(length);
        var currentResult = new List<char[]>(totalItem);
        var previousResult = new List<char[]>(totalItem);
        int taskLength = 1000;
        previousResult.Add(new char[] { items[currentPosition] });

        while (currentPosition > 0)
        {
            currentResult.Clear();
            int count = previousResult.Count;
            int numTask = count / taskLength;
            if (count % taskLength != 0)
                numTask += 1;

            Task<List<char[]>>[] tasks = new Task<List<char[]>>[numTask];
            int startTask = 0;
            var position = currentPosition;
            int taskInd = 0;
            while (taskInd < numTask)
            {
                tasks[taskInd++] = Task.Factory.StartNew(e =>
                {
                    int start = (int)e;
                    int end = start + taskLength;
                    if (end > previousResult.Count)
                        end = previousResult.Count;
                    var mylist = new List<char[]>((end - start) * (previousResult[0].Length + 1));
                    for (int i = start; i < end; i++)
                    {
                        mylist.AddRange(AddItem(previousResult[i], items[position - 1]));
                    }
                    return mylist;
                }, startTask);
                startTask += taskLength;
            }
            Task.WaitAll(tasks);
            foreach (var task in tasks)
            {
                currentResult.AddRange(task.Result);
                task.Dispose();
            }

            if (currentPosition - 1 > 0)
            {
                previousResult.Clear();
                previousResult.AddRange(currentResult);
            }

            currentPosition--;
        }

        return currentResult;
    }
}

Inside of Calculate function, the first item is added to the tempList and each character is processed according to currentPosition.

AddItem function is responsible for adding current item to each possible position of previous permutation and returns a list as a result.

Parallel Version

The algorithm can also be implemented parallelly to produce results. The function CalculateParallel takes the same input like Calculate method but processes input using multithreading. Based on the taskLength variable, we create some tasks and each task will be sent the start index of which array it should start processing from and finally, we add the result from each task to the current result.

Points of Interest

As it is mentioned above, we used dynamic programming to generate a list of permutation.This algorithm simply uses previous results to generate new results and also doesn't take into account the ordering. As you noticed in each iteration, we need to clear previous results and insert them again which impacts performance. In my next tip, we will take another approach to improve memory usage.

History

• 04/04/2015: Version 1.0