## 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: ");
Console.Write("\nEnter combination k-value: ");
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
{
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