Advertisements
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

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.

Lets 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 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 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 };
}
Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

Categories

%d bloggers like this: