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 [email protected].