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].

comments powered by Disqus

Featured

Subscribe on YouTube