Posted by: jsonmez | November 24, 2009

Importunate Permutations

Here is an interesting programming problem:

Calculate all the permutations of a particular string.

For Example:

The permutations of “abc” are







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.

Lets start with N, we will define a function permutation which will give us the permutations of any string.

permutation(“a”) =


permutation(“ab”) =

“a” + permutation(“b”)

“b” + permutation(“a”)

permutation(“abc”) =

“a” + permutation(“bc”)

“b” + permutation(“ac”)

“c” + permutation(“ab”)


foreach character c in x

c + permutation(x remove c)

Looking it is in C# code it would like 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 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);

        return new string[] { s };

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: