15,964,202 members
Articles / Programming Languages / C#
Tip/Trick

Calculating Permutation Using Dynamic Programming

Rate me:
5 Apr 2015CPOL3 min read 40.1K   306   12   2
Calculating all permutation in C# without using recursion

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:

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

The application accepts inputs from the user which is a `string` and will be passed as an array of `char`s 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.

C#
```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
while (currentPosition > 0)
{
currentResult.Clear();
foreach (var item in previousResult)
{
}
if (currentPosition - 1 > 0)
{
previousResult.Clear();
}
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++;
}

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);

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

var position = currentPosition;
{
{
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++)
{
}
return mylist;
}
{
}

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

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

Written By
Software Developer (Senior)
Poland
I am a senior .Net developer who has experience in Web and Desktop application.
I am also interested in Forex (Mql4 programming ) and at my leisure time I take time on it.