Improved Permutations with the BigInteger Data Type: Listing 4

Complete demo program code.

• By James McCaffrey
• 09/04/2012

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