I decided to refactor some old C# code for mathematical permutations. A zero-based permutation of order n is a rearrangement of the integers 0 to n-1. For example, the first zero-based permutation of order 4 is [0,1,2,3] and another permutation is [1,3,0,2].

I usually define a Permutation class but for mental exercise I figured I’d use a lightweight approach and just use a basic int[] array.

A key function when working with permutations is a Factorial(n) function because the total number of permutations of order n is n! = Factorial(n). For example, if n = 4, there are 4! = 4 * 3 * 2 * 1 = 24 distinct permutations. Because the number of permutations can be astronomically large, it’s necessary to use the C# BigInteger type which can handle arbitrarily large integers.

Another key function related to permutations is a Successor() function. The usual way to define an ordering of permutations is to use lexicographical order. For order n = 3, all permutations in lexicographical order are:

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

If each permutation is considered an integer, they increase from smallest to largest, this case from 12 to 210. The code to implement a Successor function is quite tricky.

For a Successor() function it’s necessary to determine what to do with the last permutation. In my demo code I return null. Another possibility is to throw an Exception of loop back and return the first permutation.

“Permutation City” is a 1994 science fiction novel by author Greg Egan. In the story, “Copies” are simulated humans that live in the “Autoverse”. The book won the John W. Campbell Award for the best sci fi novel of 1995. The book was interesting but too philosophical for my taste. Here is a permutation of three different covers for the novel.

Demo code. Replace “lt”, “gt”, “lte”, “gte” with Boolean operator symbols.

using System;  // .NET 6.0
using System.Numerics;

namespace Combinations // classic style template
{
  internal class Program
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin .NET 6 perms demo ");

      // define a permutation as an array of int
      //int[] p = new int[] { 0, 1, 2, 3 };
      int[] p = MakePerm(4);  // [0,1,2,3]
      Console.WriteLine("\nInitial perm order 4 is: ");
      ShowPerm(p);

      BigInteger numPerms = Factorial(4);
      Console.WriteLine("\nnumber of perms order 4 is: ");
      Console.WriteLine(numPerms);

      numPerms = Factorial(20);
      Console.WriteLine("\nnumber of perms order 20 is: ");
      Console.WriteLine(numPerms.ToString("N0"));

      Console.WriteLine("\nAll permutations order 4: ");
      while (p != null)
      {
        ShowPerm(p);
        p = Successor(p);
      }

      Console.WriteLine("\nEnd permutations demo ");
      Console.ReadLine();
    } // Main

    static int[] MakePerm(int order)
    {
      int[] result = new int[order];
      for (int i = 0; i "lt" order; i++)
        result[i] = i;
      return result;
    }

    static void ShowPerm(int[] perm)
    {
      int order = perm.Length;
      for (int i = 0; i "lt" order; ++i)
        Console.Write(perm[i] + " ");
      Console.WriteLine("");
    }

    static bool IsLast(int[] perm)
    {
      // is perm like [5,4,3,2,1,0] ?
      int order = perm.Length;
      if (perm[0] != order - 1) return false;
      if (perm[order-1] != 0) return false;
      for (int i = 0; i "lt" order - 1; ++i)
      {
        if (perm[i] "lt" perm[i + 1])
          return false;
      }
      return true;
    }

    static int[] Successor(int[] perm)
    {
      int order = perm.Length;  // [0,1,2,3,4] is order 5

      if (IsLast(perm) == true)
        return null;
     
      // is perm like [4,3,2,1,0] and so no successor?
      int[] result = new int[order];
      for (int k = 0; k "lt" order; ++k)  // make copy
        result[k] = perm[k];

      int left, right;

      left = order - 2;  // Find left value 
      while ((result[left] "gt" result[left + 1])
        && (left "gte" 1))
        --left;

      right = order - 1;  // find right; first value gt left
      while (result[left] "gt" result[right])
        --right;

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

      int i = left + 1;  // order the tail
      int j = order - 1;
      while (i "lt" j)
      {
        tmp = result[i];
        result[i++] = result[j];
        result[j--] = tmp;
      }

      return result;
    }

    static BigInteger Factorial(int n)
    {
      if (n == 0 || n == 1)
        return BigInteger.One;

      // BigInteger ans = BigInteger.One;
      BigInteger ans = BigInteger.Parse("1");
      for (int i = 1; i "lte" n; ++i)
        ans *= i;
      return ans;
    }

  } // Program

} // ns