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:
| public static List<string> Permutations(string s) | |
| { | |
| if (s.Length == 1) | |
| { | |
| return new List<string> { s }; | |
| } | |
| List<string> permutations = new List<string>(); | |
| foreach (char c in s) | |
| { | |
| string leftOver = s.Replace(c.ToString, ""); | |
| List<string> stringsReturned = Permutations(leftOver); | |
| foreach (string permutation in stringsReturned) | |
| { | |
| permutations.Add(c + permutation); | |
| } | |
| } | |
| return permutations; | |
| } |
Update: Here is a pretty slick example in LINQ that I got from a stackoverflow.com question.
| public static IEnumerable<string> GetPermutations(string s) | |
| { | |
| if (s.Count() > 1) | |
| return from ch in s | |
| from permutation in GetPermutations(s.Remove(s.IndexOf(ch), 1)) | |
| select string.Format("{0}{1}", ch, permutation); | |
| else | |
| return new string[] { s }; | |
| } |
For a better understanding of permutations, check out this short booklet on How to Understand Permutations and Computations .
