Improved Permutations with the BigInteger Data Type: Listing 3

The Permutation Element method.

public Permutation Element(BigInteger k)
{
  if (k >= Factorial(this.n))
    throw new Exception("k too large in Element");
  Permutation result = new Permutation(this.n);

  int[] factoradic = new int[this.n]; // factoradic of k
  for (int j = 1; j <= n; ++j)  // note: skip [0]
  {
    factoradic[n - j] = (int)(k % j);  // remainder always an int
    k /= j;
  }

  for (int i = 0; i < n; ++i)
    ++factoradic[i];
 
  result.data[n - 1] = 1; // last value set to 1
  for (int i = n - 2; i >= 0; --i)
  {
    result.data[i] = factoradic[i];  // copy factoradic
    for (int j = i + 1; j < n; ++j)  // inc all values to right . . 
    {
      if (result.data[j] >= result.data[i]) // that are < factoradic
        ++result.data[j];
    }
  }

  for (int i = 0; i < n; ++i) // make result 0-based
    --result.data[i];

  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 jamccaff@microsoft.com.

comments powered by Disqus

Featured

.NET Insight

Sign up for our newsletter.

Terms and Privacy Policy consent

I agree to this site's Privacy Policy.

Upcoming Events