{"id":5,"date":"2009-11-24T18:07:37","date_gmt":"2009-11-24T18:07:37","guid":{"rendered":"https:\/\/simpleprogrammer.com\/?p=5"},"modified":"2018-02-23T10:50:22","modified_gmt":"2018-02-23T15:50:22","slug":"importunate-permutations","status":"publish","type":"post","link":"https:\/\/simpleprogrammer.com\/importunate-permutations\/","title":{"rendered":"Importunate Permutations"},"content":{"rendered":"

Here is an interesting programming problem:\u00a0Calculate all the permutations of a string.<\/p>\n

For example, the permutations of “abc” are:<\/p>\n

abc<\/p>\n

acb<\/p>\n

bac<\/p>\n

bca<\/p>\n

cab<\/p>\n

cba<\/p>\n

It is not as easy of a problem as it seems, but it has a rather simple solution.<\/p>\n

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.<\/p>\n

A good way to solve these kinds of problems is to start with N, N+1, N+2, then solve for N+x.<\/p>\n

Let’s start with N; we will define a function permutation which will give us the permutations of any string.<\/p>\n

permutation(“a”) =<\/p>\n

“a”<\/p>\n

permutation(“ab”) =<\/p>\n

“a” + permutation(“b”)<\/p>\n

“b” + permutation(“a”)<\/p>\n

permutation(“abc”) =<\/p>\n

“a” + permutation(“bc”)<\/p>\n

“b” + permutation(“ac”)<\/p>\n

“c” + permutation(“ab”)<\/p>\n

permutation(x)<\/p>\n

foreach character c in x<\/p>\n

c + permutation(x remove c)<\/p>\n

Looking at it in C# code, it would look something like:<\/p>\n