# Creating a list of all permutations of a text or number

## Problem

Taking a string or an integer and listing every conceivable permutation is a popular task in programming interviews (albeit not in my experience with interviews).

Is there an example of how this is done, as well as the logic behind it?

I’ve seen a few code bits, but they weren’t clearly commented or explained, making them difficult to understand.

## Solution #1

First and foremost, it smells like recursion!

Because you were also curious about the theory, I did my best to describe it in layman’s terms. Most of the time, I believe recursion is extremely simple. There are simply two steps to remember:

In human language:

On http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/, I discovered the pseudocode:

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

C#

OK, here’s something more elaborate from http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html (and because it’s marked c #): Although it is somewhat lengthy, I chose to replicate it nevertheless so that the post does not rely on the original.

ABC, ACB, BAC, BCA, CAB, and CBA are abbreviations for ABC, ACB, BAC, BCA, CAB, and 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);
}
}
``````

## Solution #2

If LINQ is allowed to be used, it’s only two lines of code. Please find my response below.

EDIT

This is my generic function for returning all 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);
``````

a list of integer-lists as output:

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

This function requires.net 3.5 or higher because it uses LINQ.

## Solution #3

I’ve discovered the answer. It was originally written in Java, but I rewrote it in C#. I hope it is of assistance to you.

The C# code for this is as follows:

``````static void Main(string[] args)
{
string str = "ABC";
char[] charArry = str.ToCharArray();
Permute(charArry, 0, 2);
}

static void Permute(char[] arry, int i, int n)
{
int j;
if (i==n)
Console.WriteLine(arry);
else
{
for(j = i; j <=n; j++)
{
Swap(ref arry[i],ref arry[j]);
Permute(arry,i+1,n);
Swap(ref arry[i], ref arry[j]); //backtrack
}
}
}

static void Swap(ref char a, ref char b)
{
char tmp;
tmp = a;
a=b;
b = tmp;
}
``````

## Solution #4

There is no need for recursion; here is some useful information regarding this solution.

``````var values1 = new[] { 1, 2, 3, 4, 5 };

foreach (var permutation in values1.GetPermutations())
{
Console.WriteLine(string.Join(", ", permutation));
}

var values2 = new[] { 'a', 'b', 'c', 'd', 'e' };

foreach (var permutation in values2.GetPermutations())
{
Console.WriteLine(string.Join(", ", permutation));
}

``````

I’ve been using this approach for years; it calculates each permutation in O(N) time and space.

``````public static class SomeExtensions
{
public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> enumerable)
{
var array = enumerable as T[] ?? enumerable.ToArray();

var factorials = Enumerable.Range(0, array.Length + 1)
.Select(Factorial)
.ToArray();

for (var i = 0L; i < factorials[array.Length]; i++)
{
var sequence = GenerateSequence(i, array.Length - 1, factorials);

yield return GeneratePermutation(array, sequence);
}
}

private static IEnumerable<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> sequence)
{
var clone = (T[]) array.Clone();

for (int i = 0; i < clone.Length - 1; i++)
{
Swap(ref clone[i], ref clone[i + sequence[i]]);
}

return clone;
}

private static int[] GenerateSequence(long number, int size, IReadOnlyList<long> factorials)
{
var sequence = new int[size];

for (var j = 0; j < sequence.Length; j++)
{
var facto = factorials[sequence.Length - j];

sequence[j] = (int)(number / facto);
number = (int)(number % facto);
}

return sequence;
}

static void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}

private static long Factorial(int n)
{
long result = n;

for (int i = 1; i < n; i++)
{
result = result * i;
}

return result;
}
}
``````

## Solution #5

``````class Program
{
public static void Main(string[] args)
{
Permutation("abc");
}

static void Permutation(string rest, string prefix = "")
{
if (string.IsNullOrEmpty(rest)) Console.WriteLine(prefix);

// Each letter has a chance to be permutated
for (int i = 0; i < rest.Length; i++)
{
Permutation(rest.Remove(i, 1), prefix + rest[i]);
}
}
}
``````