Saturday, July 17, 2010

Generating combinations in lexicographical order using Java

Below is a Java port of the algorithm by James McCaffrey as presented in the MSDN article Generating the mth Lexicographical Element of a Mathematical Combination.

Please do take into consideration that this implementation only uses int as Java does not allow array indexing with long. This means that the valid input range is more restricted. Watch out for overflows!

/**
* Based on the Combinadic Algorithm explained by James McCaffrey
* in the MSDN article titled: "Generating the mth Lexicographical
* Element of a Mathematical Combination"
* <http://msdn.microsoft.com/en-us/library/aa289166(VS.71).aspx>
*
* @author Ahmed Abdelkader
* Licensed under Creative Commons Attribution 3.0
* <http://creativecommons.org/licenses/by/3.0/us/>
*/
public class Combinations {
/** returns the mth lexicographic element of combination C(n,k) **/
public static int[] element(int n, int k, int m) {
int[] ans = new int[k];

int a = n;
int b = k;
int x = (choose(n, k) - 1) - m; // x is the "dual" of m

for (int i = 0; i < k; ++i) {
a = largestV(a, b, x); // largest value v, where v < a and vCb < x
x = x - choose(a, b);
b = b - 1;
ans[i] = (n - 1) - a;
}

return ans;
}

/** returns the largest value v where v < a and Choose(v,b) <= x **/
public static int largestV(int a, int b, int x) {
int v = a - 1;

while (choose(v, b) > x)
--v;

return v;
}

/** returns nCk - watch out for overflows **/
public static int choose(int n, int k) {
if (n < 0 || k < 0)
return -1;
if (n < k)
return 0;
if (n == k || k == 0)
return 1;

int delta, iMax;

if (k < n - k) {
delta = n - k;
iMax = k;
} else {
delta = k;
iMax = n - k;
}

int ans = delta + 1;

for (int i = 2; i <= iMax; ++i) {
ans = (ans * (delta + i)) / i;
}

return ans;
}
}
The code below produced the output that follows:
public static void main(String[] args) {
int n = 5, k = 3;
int total = choose(n, k);
for(int i = 0; i < total; i ++) {
for(int x : element(n, k, i))
System.out.print(x + " ");
System.out.println();
}
}

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