## Generating All Permutations

Two of the most common and fundamental programming tasks are generating all possible permutations, and generating all possible combinations. Last week I spent some time looking at what I’d find on the Internet about these two problems. I was surprised by the large number of Web pages and blogs which have really, really bad information. First, the terms permutations and combinations, are used incorrectly on many Web sites. A mathematical permutation of order (size) n is a rearrangement of the numbers 0 through n-1. For example, if n=3, then all possible permutations are {0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0}. Here I’ve listed the permutations in lexicographical order. A mathematical combination of order (n,k) is a subset of size k of the numbers 0 through n-1 where order does not matter. For example, all combinations of order (5,3) in lexicographical order are {0,1,2}, {0,1,3}, {0,1,4}, {0,2,3}, {0,2,4}, {0,3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}. Anyway, listed below is a tiny class, written in C#, with error-checking removed, that will generate all possible permutations. The class can be called like this:

static void Main(string[] args)
{
Console.Write("\nEnter permutation order (n): ");
int n = int.Parse(Console.ReadLine());
Console.WriteLine("\nAll permutations: \n");
Permutation p = new Permutation(n);
while (p != null) {
Console.WriteLine(p.ToString());
p = p.Successor();
}
Console.WriteLine("\nDone");
}

Notice the approach is to define a Successor() method which returns the next permutation object, or null if we are at the last permutation. Here’s the class:

public class Permutation
{
public readonly int n;
public readonly int[] data;

public Permutation(int n) {
this.n = n;
this.data = new int[n];
for (int i = 0; i < n; ++i)
data[i] = i;
}

public override string ToString()
{
string s = "( ";
for (int i = 0; i < n; ++i)
s += data[i] + " ";
s += ")";
return s;
}

public Permutation Successor()
{
Permutation result = new Permutation(n);
int left, right;
for (int i = 0; i < n; ++i)
result.data[i] = this.data[i];

left = result.n- 2;  // Step #1 – Find left value
while ((result.data[left] > result.data[left + 1]) && (left >= 1))
–left;

if ((left == 0) && (this.data[left] > this.data[left + 1]))
return null;
right = result.n – 1;  // Step #2 – find right value
while (result.data[left] > result.data[right])
–right;

int temp = result.data[left];  // Step #3 – left and right
result.data[left] = result.data[right];
result.data[right] = temp;

int x = left + 1;              // Step #4 – order the tail
int y = result.n – 1;
while (x < y) {
temp = result.data[x];
result.data[x++] = result.data[y];
result.data[y–] = temp;
}
return result;
}
} // Permutation