## Friday, July 15, 2011

### Introduction

What is permutation ? For a String, it is just a rearrangement of letters.
For example, consider the String "abc", the list all permutations would be :
```["abc","acb","bac","bca","cab","cba"]
```

### Algorithm

There are many algorithms to generate permutation systematically. But not all of them are easily understandable. Instead of presenting the most efficient way of permutation generation, I am going to present a simple one that is straight forward.

Consider the String "abc" again. We can choose any letter to start in our permutation, so let's choose the letter "a". Now the problem reduced to finding all permutations of "bc", which is an obvious problem, the permutation list of "bc" is just ["bc","cb"].

Since the permutation can be started with any letter, we arrive at the following algorithm :

### Steps to find : permutation("abc")

1. fix "a" and find permutation("bc")
2. fix "b" and find permutation("ac")
3. fix "c" and find permutation("ab")

We can extends it to find permutation of 4 letters

### Steps to find : permutation("abcd")

1. fix "a" and find permutation("bcd")
2. fix "b" and find permutation("acd")
3. fix "c" and find permutation("abd")
4. fix "d" and find permutation("abc")

This naturally leads to a recursive algorithm

### Demonstration

As usual, I would provide a full runnable demo in my articles. Compile and run the following program :

### Trace

```Level 1 Expand
perm("","abc")  // head is emtpy and tail is "abc"
perm("a","bc") // remove "a" from tail and append it to head
perm("b","ac") // remove "b" from tail and append it to head
perm("c","ab") // remove "c" from tail and append it to head
```

```Level 2 Expand
perm("","abc")  // head is emtpy and tail is "abc"
perm("a","bc") // remove "a" from tail and append it to head
perm("ab","c")  // remove "b" from tail and append to head
perm("ac","b")  // remove "c" from tail and append to head
perm("b","ac") // remove "b" from tail and append it to head
perm("ba","c")  // remove "a" from tail and append it to head
perm("bc","a")  // remove "c" from tail and append it to head
perm("c","ab") // remove "c" from tail and append it to head
perm("ca","b")  // remove "a" from tail and append it to head
perm("cb","a")  // remove "b" from tail and append it to head
```

Whenever the tail contains only one character, the recursion is terminated and a permutation will be printed. Hence the above trace result in 6 permutations :
```["abc","acb","bac","bca","cab",cba"]
```