dotnetdev - 1 year ago 188

Python 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 Source

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:

- The first step
- 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) -> aIf 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) ->

abb + perm(a) ->

baFurther: for each character in the set: return a character, concatenated with a perumation of > the rest of the set

perm(abc) ->

a + perm(bc) -->

abc,acbb + perm(ac) -->

bac,bcac + perm(ab) -->

cab,cbaperm(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;
a ^= b;
b ^= a;
a ^= b;
}
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);
}
}
```