Importunate Permutations

Written By John Sonmez

Here is an interesting programming problem: Calculate all the permutations of a string.

For example, the permutations of “abc” are:

abc

acb

bac

bca

cab

cba

It is not as easy of a problem as it seems, but it has a rather simple solution.

Many times recursion is actually more complex to understand than a non-recursive solution, but in this case recursion is an elegant and simple solution.

A good way to solve these kinds of problems is to start with N, N+1, N+2, then solve for N+x.

Let's start with N; we will define a function permutation which will give us the permutations of any string.

permutation(“a”) =

“a”

permutation(“ab”) =

“a” + permutation(“b”)

“b” + permutation(“a”)

permutation(“abc”) =

“a” + permutation(“bc”)

“b” + permutation(“ac”)

“c” + permutation(“ab”)

permutation(x)

foreach character c in x

c + permutation(x remove c)

Looking at it in C# code, it would look something like:

Update: Here is a pretty slick example in LINQ that I got from a stackoverflow.com question.

For a better understanding of permutations, check out this short booklet on How to Understand Permutations and Computations .