Improved Permutations with the BigInteger Data Type: Listing 4

Complete demo program code.

using System;
using System.Numerics;


namespace ImprovedPermutations
{
  class PermutationsProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin improved permutations with BigInteger demo\n");

      string[] names = new string[] { "Adam", "Barb", "Carl" };
      Permutation p2 = new Permutation(3); // 0th
      p2 = p2.Successor(); // 1
      p2 = p2.Successor(); // 2
      p2 = p2.Successor(); // 3
      p2 = p2.Successor(); // 4
      names = p2.ApplyTo(names);
      Console.WriteLine("\nThe 4th permutation element applied to 'Adam', 'Barb', 'Carl' is:");
      for (int i = 0; i < names.Length; ++i)
        Console.Write(names[i] + " ");
      Console.WriteLine("\n");



      int n = 3;
      Permutation p1 = new Permutation(n);
      Console.WriteLine("All permutations for order n = 3 are:\n");
      int ct = 0;
      while (p1 != null)
      {
        Console.WriteLine(ct + ": " + p1.ToString());
        p1 = p1.Successor();
        ++ct;
      }

      //Permutation p2 = new Permutation(n);
      //string[] names = new string[] { "Adam", "Barb", "Carl" };
      //p2 = p2.Element(4);
      //names = p2.ApplyTo(names);
      //Console.WriteLine("\nThe 4th permutation element applied to 'Adam', 'Barb', 'Carl' is:");
      //for (int i = 0; i < names.Length; ++i)
      //  Console.Write(names[i] + " ");
      //Console.WriteLine("\n");

      n = 30;
      BigInteger nFactorial = Permutation.Factorial(n);
      Console.WriteLine("The .NET int.MaxValue is " + int.MaxValue.ToString("#,###"));
      Console.WriteLine("\nFor a permutation with order n = 30 there are n! = \n");
      Console.WriteLine(nFactorial.ToString("#,###"));
      Console.WriteLine("\npossible permutation elements.\n");

      Permutation p3 = new Permutation(n);
      BigInteger k = BigInteger.Parse("999999999999999999999999999999");
      p3 = p3.Element(k);
      Console.WriteLine("\nThe " + k.ToString("#,###") + "th element for order n = 30 is:");
      Console.WriteLine(p3.ToString());

      Console.WriteLine("\nEnd permutations demo\n");
      Console.ReadLine();
    }
  } // class PermutationsProgram

  public class Permutation
  {
    private int n; // order
    private int[] data;

    public Permutation(int n)
    {
      this.n = n;
      this.data = new int[n];
      for (int i = 0; i < n; ++i)
        this.data[i] = i;
    }

    public static BigInteger Factorial(int k)
    {
      if (k == 0) return 1;
      BigInteger ans = 1;
      for (int i = 1; i <= k; ++i)
        ans *= i;
      return ans;
    }

    public Permutation Successor()
    {
      if (data[0] == n - 1 && data[n - 1] == 0)
        return null;

      Permutation result = new Permutation(this.n);

      for (int idx = 0; idx < result.n; ++idx)  // copy curr data into result
        result.data[idx] = this.data[idx];
 
      int left, right;

      left = n - 2;  // Find left value 
      while ((result.data[left] > result.data[left + 1]) && (left >= 1))
        --left;

      right = n - 1;  // find right; first value > left
      while (result.data[left] > result.data[right])
        --right;

      int tmp = result.data[left];  // swap [left] and [right]
      result.data[left] = result.data[right];
      result.data[right] = tmp;

      int i = left + 1;              // order the tail
      int j = n - 1;

      while (i < j)
      {
        tmp = result.data[i];
        result.data[i++] = result.data[j];
        result.data[j--] = tmp;
      }

      return result;
    }

    public string[] ApplyTo(string[] arr)
    {
      string[] result = new string[n];
      for (int i = 0; i < n; ++i)
        result[i] = arr[data[i]];
      return result;
    }

    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;
    }

    public override string ToString()
    {
      string s = "( ";
      for (int i = 0; i < data.Length; ++i)
        s += data[i] + " ";  // consider StringBuilder
      s += ")";
      return s;
    }

  } // class Permutation


} // ns

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.