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!
/**The code below produced the output that follows:
* 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;
}
}
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
3 comments:
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.
@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.
You don't need to make the parameters n and k long's or your array for that matter. Only the return value of Choose() needs to be long. For instance the largest lotto I know of is Keno which has 70 balls and 20 selections. So you would be using parameters like Choose(70, 20). Anything higher would result in a long overflow as well.
Also you could implement the reverse of the Function Element to translate the numbers back into combination index. Which works as follows:-
Public Function ElementRev(ByVal aAns() As Integer) As Long
Dim iMaxCombs As Long = Choose(miTypes, miChosen) - 1
Dim iTypes As Integer = miTypes ' Types to choose from (n)
Dim iArrLen As Integer = (aAns.Length - 1)
Dim iType As Integer = (miTypes - 1)
For iIdx As Integer = 0 To iArrLen
aAns(iIdx) = (iType - aAns(iIdx))
Next
' x is the "dual" of iCombIndex
Dim iChosen As Integer = 0
Dim iCombs As Long = 0
For iIdx As Integer = iArrLen To 0 Step -1
Dim iLargeV As Integer = aAns(iIdx)
iChosen += 1
iTypes = iLargeV
iCombs += Choose(iLargeV, iChosen)
Next
' Return Element Index
Return (iMaxCombs - iCombs)
End Function
Post a Comment