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 .