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, WA. James has worked on several key Microsoft products such as Internet Explorer and Bing. James can be reached at jamccaff@microsoft.com.