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(, 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

comments powered by Disqus


.NET Insight

Sign up for our newsletter.

Terms and Privacy Policy consent

I agree to this site's Privacy Policy.

Upcoming Events