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

2 comments:

PeterVermont said...

I know this is old but I still found it useful -- particularly the link to the original article and code which I was unaware of.

I think you have unnecessarily limited your code. While java cannot use longs for indexing which affects n and k this does not require that the index returned from choose be restricted to an int.

Ahmed Abdelkader said...

@PeterVermont: Good point. Thanks for pointing that out. It seems all ints can be replaced by longs except the second function arguments. However, the code really should check for overflows. I hope it is still useful.