Generating All Combinations

A few blog posts ago I described generating all possible permutations. I mentioned that 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}. Here is a class, written in C# (with error-checking removed) that will generate all possible combinations. The class can be called like this:
 
static void Main(string[] args)
{
  Console.Write("\nEnter combination n-value: ");
  int n = int.Parse(Console.ReadLine());
  Console.Write("\nEnter combination k-value: ");
  int k = int.Parse(Console.ReadLine());
  Console.WriteLine("\nAll combinations: \n");
  Combination c = new Combination(n, k);
  while (c != null) {
    Console.WriteLine(c.ToString());
    c = c.Successor();
  }
  Console.WriteLine("\nDone");
}
 
 
 
Notice the approach is to define a Successor() method which returns the next combination object, or null if we are at the last combination. Here’s the class:
 
public class Combination
{
  private readonly int n;
  private readonly int k;
  private readonly int[] data;
  public Combination(int n, int k)
  {
    this.n = n;
    this.k = k;
    this.data = new int[k];
    for (int i = 0; i < k; ++i) {
      data[i] = i;
    }
  } // ctor()
  public override string ToString()
  {
    string s = "{ ";
    for (int i = 0; i < k; ++i)
      s += data[i] + " ";
    s += "}";
    return s;
  }
  public Combination Successor()
  {
    if (data[0] == n – k) // last combination element
      return null;
    Combination ans = new Combination(n, k);
    int i;
    for (i = 0; i < k; ++i)
      ans.data[i] = this.data[i];
    for (i = k – 1; i > 0 && ans.data[i] == n – k + i; –i)
      ;
    ++ans.data[i];
    for (int j = i; j < k – 1; ++j)
      ans.data[j + 1] = ans.data[j] + 1;
    return ans;
  } // Successor()
} // class Combination
 
This entry was posted in Software Test Automation. Bookmark the permalink.