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

comments powered by Disqus

Featured

  • Java on Visual Studio Code Going Cloud Native

    Cloud-native development figures prominently in a new roadmap published by Microsoft's Java on Visual Studio Code dev team.

  • Speed Lines Graphic

    Quantum-Inspired Annealing Using C# or Python

    Dr. James McCaffrey of Microsoft Research explains a new idea that slightly modifies standard simulated annealing by borrowing ideas from quantum mechanics.

  • Visual Studio 2022 v17.1 Preview 3 Improves Web Tools

    Microsoft quietly shipped Visual Studio 2022 v17.1 Preview 3 with enhancements to web tools.

  • Progress Telerik Adds 20-Plus Components for Blazor, .NET MAUI and WinUI

    The R1 2022 release of Progress Telerik development tooling adds more than 20 new components to the Blazor, .NET MAUI and WinUI offerings.

Upcoming Events