Improved Combinations with the BigInteger Data Type: Listing 4.
Improved mth lexicographical element of a combination.
public Combination Element(BigInteger m)
{
BigInteger maxM = Choose(this.n, this.k) - 1;
if (m > maxM)
throw new Exception("m value is too large in Element");
int[] ans = new int[this.k];
int a = this.n;
int b = this.k;
BigInteger x = maxM - m; // x is the "dual" of m
for (int i = 0; i < this.k; ++i)
{
ans[i] = LargestV(a, b, x); // see helper below
x = x - Choose(ans[i], b);
a = ans[i];
b = b - 1;
}
for (int i = 0; i < this.k; ++i)
ans[i] = (n - 1) - ans[i];
Combination result = new Combination(this.n, this.k);
ans.CopyTo(result.data, 0);
return result;
}
About the Author
Dr. James McCaffrey works for Microsoft Research in Redmond, Wash. He has worked on several Microsoft products including Azure and Bing. James can be reached at [email protected].