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
 
Advertisements
This entry was posted in Software Test Automation. Bookmark the permalink.