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

  • GitLab Takes Over VS Code Extension, Plans Improvements

    DevOps specialist GitLab has officially taken over the control of a GitLab extension for Microsoft's open source, cross-platform Visual Studio Code editor.

  • VS Code Python Tool Now Does Native Notebooks

    The Python Extension for VS Code Insiders team is previewing the newest implementation of notebooks, used frequently in data science with offerings such as Jupyter Notebooks.

  • As .NET 5 Nears, Content/Documentation Reorganization Starts

    A GitHub project is seeking to reorganize documentation and developer content in advance of the November debut of .NET 5, a unification of all things .NET that combines. .NET Core and other components.

  • Windows Devs Get Cross-Platform Page, Issues Repo

    Developers doing their coding on the Windows OS have received two new resource gifts from Microsoft: a new landing page for those using cross-platform technologies and a new GitHub repo with which to report issues to Windows engineering teams.Developers doing their coding on the Windows OS have received two new resource gifts from Microsoft: a new landing page for those using cross-platform technologies and a new GitHub repo with which to report issues to Windows engineering teams.

  • What's New in Entity Framework Core 5.0 Preview 7

    Microsoft shipped the seventh preview of Entity Framework Core 5.0, boosting its data access technology with a factory to create DbContext instances and more.

.NET Insight

Sign up for our newsletter.

Terms and Privacy Policy consent

I agree to this site's Privacy Policy.

Upcoming Events