Permutation Generator

Related Articles

• Combination Generator

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"]