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 : smells like recurision of course!

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

1. The first step
2. All the other steps (with 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 have 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 characte in set : return charachter, concatenated with perumation 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(....) ....

The pseudocode I found 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 exaple, if "ABC" has been supplied, should spill out:

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

using System;

namespace ConsoleApplication3
{
        class Permute
        {
                 private void swap (ref char a, ref char b)
                 {
                        if(a==b)return;
                        a^=b;
                        b^=a;
                        a^=b;
                  }

                  public void setper(char[] list)
                  {
                        int x=list.Length-1;
                        go(list,0,x);
                  }

                  private void go (char[] list, int k, int m)
                  {
                        int i;
                        if (k == m)
                           {
                                 Console.Write (list);
                                 Console.WriteLine (" ");
                            }
                        else
                             for (i = k; i <= m; i++)
                            {
                                   swap (ref list[k],ref list[i]);
                                   go (list, k+1, m);
                                   swap (ref list[k],ref list[i]);
                            }
                   }
         }

         class Class1
        {
               static void Main()
               {

                      Permute p = new Permute();
                      string c="sagiv";
                       char []c2=c.ToCharArray ();
                       /*calling the permute*/
                      p.setper(c2);
                  }
           }
}

Answer 2

First of all, sets have permutations, not strings or integers, so I'll just assume you mean "the set of characters in a string."

Note that a set of size n has n! n-permutations.

The following pseudocode (from Wikipedia), called with k = 1...n! will give all the permutations:

function permutation(k, s) {
    for j = 2 to length(s) {
        swap s[(k mod j) + 1] with s[j]; // note that our array is indexed starting at 1
        k := k / j; // integer division cuts off the remainder
    }
    return s;
}

Here's the equivalent Python code (for 0-based array indexes):

def permutation(k, s):
    r = s[:]
    for j in range(2, len(s)+1):
        r[j-1], r[k%j] = r[k%j], r[j-1]
        k = k/j+1
    return r

Answer 3

Here's a good article covering three algorithms for finding all permutations, including one to find the next permutation.

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

C++ and Python have built-in next_permutation and itertools.permutations functions respectively.

Answer 4

Here's a purely functional F# implementation:

let factorial i =
    let rec fact n x =
        match n with
        | 0 -> 1
        | 1 -> x
        | _ -> fact (n-1) (x*n)
    fact i 1

let swap (arr:'a array) i j = [| for k in 0..(arr.Length-1) -> if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |]

let rec permutation (k:int,j:int) (r:'a array) =
    if j = (r.Length + 1) then r
    else permutation (k/j+1, j+1) (swap r (j-1) (k%j))

let permutations (source:'a array) = seq { for k = 0 to (source |> Array.length |> factorial) - 1 do yield permutation (k,2) source }

Performance can be greatly improved by changing swap to take advantage of the mutable nature of CLR arrays, but this implementation is thread safe with regards to the source array and that may be desirable in some contexts. Also, for arrays with more than 16 elements int must be replaced with types with greater/arbitrary precision as factorial 17 results in an int32 overflow.

Answer 5

void permute (char *str, int ptr) {
  int i, len;
  len = strlen(str);
  if (ptr == len) {
    printf ("%s\n", str);
    return;
  }

  for (i = ptr ; i < len ; i++) {
    swap (&str[ptr], &str[i]);
    permute (str, ptr + 1);
    swap (&str[ptr], &str[i]);
  }
}

You can write your swap function to swap characters.
This is to be called as permute(string, 0);