Listing all permutations of a string/integer

Question

A common task in programming interviews (not from my experience of interviews though) is to take a string or an integer and list every possible permutation.

Is there an example of how this is done and the logic behind solving such a problem?

I've seen a few code snippets but they weren't well commented/explained and thus hard to follow.

Answer 1

First of all: it smells like recursion of course!

Since you also wanted to know the principle, I did my best to explain it human language. I think recursion is very easy most of the times. You only have to grasp two steps:

1. The first step
2. All the other steps (all with the same logic)

In human language:

In short:

1. The permutation of 1 element is one element.
   
2. The permutation of a set of elements is a list each of the elements, concatenated with every permutation of the other elements.
   

Example:

If the set just has one element -->
return it.
perm(a) -> a

If the set has two characters: for each element in it: return the element, with the permutation of the rest of the elements added, like so:

perm(ab) ->

a + perm(b) -> ab

b + perm(a) -> ba

Further: for each character in the set: return a character, concatenated with a permutation of > the rest of the set

perm(abc) ->

a + perm(bc) --> abc, acb

b + perm(ac) --> bac, bca

c + perm(ab) --> cab, cba

perm(abc...z) -->

a + perm(...), b + perm(....)
....

I found the pseudocode on http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/:

makePermutations(permutation) {   if (length permutation < required length) {     for (i = min digit to max digit) {       if (i not in permutation) {         makePermutations(permutation+i)       }     }   }   else {     add permutation to list   } } 

C#

OK, and something more elaborate (and since it is tagged c #), from http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : Rather lengthy, but I decided to copy it anyway, so the post is not dependent on the original.

The function takes a string of characters, and writes down every possible permutation of that exact string, so for example, if "ABC" has been supplied, should spill out:

ABC, ACB, BAC, BCA, CAB, CBA.

Code:

class Program {     private static void Swap(ref char a, ref char b)     {         if (a == b) return;          var temp = a;         a = b;         b = temp;     }      public static void GetPer(char[] list)     {         int x = list.Length - 1;         GetPer(list, 0, x);     }      private static void GetPer(char[] list, int k, int m)     {         if (k == m)         {             Console.Write(list);         }         else             for (int i = k; i <= m; i++)             {                    Swap(ref list[k], ref list[i]);                    GetPer(list, k + 1, m);                    Swap(ref list[k], ref list[i]);             }     }      static void Main()     {         string str = "sagiv";         char[] arr = str.ToCharArray();         GetPer(arr);     } } 

Answer 2

It's just two lines of code if LINQ is allowed to use. Please see my answer here.

EDIT

Here is my generic function which can return all the permutations (not combinations) from a list of T:

static IEnumerable<IEnumerable<T>>     GetPermutations<T>(IEnumerable<T> list, int length) {     if (length == 1) return list.Select(t => new T[] { t });      return GetPermutations(list, length - 1)         .SelectMany(t => list.Where(e => !t.Contains(e)),             (t1, t2) => t1.Concat(new T[] { t2 })); } 

Example:

IEnumerable<IEnumerable<int>> result =     GetPermutations(Enumerable.Range(1, 3), 3); 

Output - a list of integer-lists:

{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1} 

As this function uses LINQ so it requires .net 3.5 or higher.