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

  • .NET for Apache Spark Debuts in Version 1.0

    The open source project .NET for Apache Spark has debuted in version 1.0, finally vaulting the C# and F# programming languages into Big Data first-class citizenship.

  • In-App Reviews Come to Xamarin.Forms Android

    Android is playing a little catch-up to iOS regarding in-app review functionality, just now coming tp Microsoft's Xamarin.Forms implementation.

  • C# Slides in Usage Ranking of Programming Languages

    "The fact that C# lost three places in the ranking of language communities during the last three years is mostly explained by its slower growth compared to C/C++ and PHP."

  • Telerik UI for Blazor Updated

    Progress announced an update to its Telerik UI for Blazor components, targeting Microsoft's open source Blazor framework that lets C# coders create web apps without having to rely upon JavaScript.

  • Infragistics Unveils UI Components for Blazor

    Infragistics, specializing in third-party UI/UX controls and tools, unveiled a new offering targeting Blazor, Microsoft's red-hot open source framework that allows for C#-based web development instead of traditional mainstay JavaScript.

Upcoming Events