The Data Science Lab

Lightweight Mathematical Permutations Using C#

Get ready to use the BigInteger data type as Dr. James McCaffrey of Microsoft Research demonstrates zero-based mathematical permutations with C#.

• By James McCaffrey
• 07/05/2022

A zero-based mathematical permutation of order n is a rearrangement of the integers 0 through n-1. For example, if n = 5, then two possible permutations are (0, 1, 2, 3, 4) and (3, 0, 4, 2, 1). The total number of permutations for order n is factorial(n), usually written as n! and calculated as n * (n-1) * (n-2) * . . 1. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.

The number of permutations gets very, very large as n increases. For example, 30! = 265,252,859,812,191,058,636,308,480,000,000, which is vastly larger than the estimated age of the universe in seconds (approximately 13.8 billion years). To deal with permutations using the C# language, it's necessary to use the BigInteger data type, which can handle arbitrarily large values.

A good way to see where this article is headed is to take a look at the screenshot of a demo program in Figure 1. The demo illustrates how to create and display a permutation of order n, compute n! using the BigInteger type, display all permutations of order n using a Successor() function, and compute a specific permutation element directly.

This article assumes you have intermediate or better programming skill with the C# language but doesn't assume you know anything about mathematical permutations. The complete demo code is presented in this article and is also available in the accompanying download. All normal error checking has been removed to keep the main ideas as clear as possible.

To create the demo program I used Visual Studio 2022 (the free Community edition) with .NET 6 (in spite of the bizarre new Console template). However, the demo has no significant dependencies, so any relatively recent versions of VS and .NET can be used.

Defining and Displaying a Permutation
The simplest possible way to define a mathematical permutation is as an array of type integer. The demo program implements a MakePerm() function as:

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

The MakePerm() function can be called like so:

int[] p = MakePerm(4);  // [0,1,2,3]
Console.WriteLine("Initial permutation order 4 is: ");
ShowPerm(p);

The ShowPerm() function is defined as:

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

An alternative design is to define a dedicated Permutation class, but in most scenarios using an integer array is simple and effective.

Defining a Factorial Function
The demo program uses the BigInteger type to define a Factorial function as:

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

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

The BigInteger type is defined in the System.Numerics namespace. In most cases 0! is defined to be 1 so the demo code does a short-circuit check. The code shows that a BigInteger value can be created by using the Parse() method, or by using the shortcut BigInteger.One or BigInteger.Zero properties.

The demo program calls the Factorial() function like this:

BigInteger numPerms = Factorial(4);
Console.WriteLine("Total permutations order 4 is: ");
Console.WriteLine(numPerms);

numPerms = Factorial(50);
Console.WriteLine("Total permutations order 50 is: ");
Console.WriteLine(numPerms.ToString("N0"));

Defining a Successor Function
All six permutations of order n = 3 are:

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

It's usual to list permutations in what's called lexicographical order. If each permutation is interpreted as an integer, they're listed from smallest (12) to largest (210). Defining a function that returns the successor permutation to a given permutation is a well-known problem. The demo program defines a Successor() function in Listing 1.

static int[] Successor(int[] perm)
{
  int order = perm.Length;  // ex: order 5

  // is perm like [4,3,2,1,0] so no successor?
  if (IsLast(perm) == true)
    return null;

  int[] result = new int[order];
  for (int k = 0; k < order; ++k)
    result[k] = perm[k];

  int left, right;

  left = order - 2;  // find left value 
  while ((result[left] > result[left + 1]) && (left >= 1))
    --left;

  right = order - 1;  // first value gt left
  while (result[left] > 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 < j)
  {
    tmp = result[i];
    result[i++] = result[j];
    result[j--] = tmp;
  }

  return result;
}

Suppose n = 6 and a current permutation is (5, 4, 1, 3, 2, 0). The successor permutation is (5, 4, 2, 0, 1, 3).

The Successor() function algorithm finds the index locations of two values to swap, in this case left = [2] and right = [4]. After the two values at left and right are swapped, the intermediate result is (5, 4, 2, 3, 1, 0). Then the algorithm finds the tail, which are the values at [left+1] to the end, and then sorts the tail values from smallest to largest. In this example the tail values of the intermediate result are (3, 1, 0). After sorting the tail values the final successor result is (5, 4, 2, 0, 1, 3).

With a Successor() function in hand, it's possible to iterate through all permutations with code like:

int[] p = MakePerm(4);  // [0,1,2,3]
Console.WriteLine("All permutations order 4: ");
while (p != null)
{
  ShowPerm(p);
  p = Successor(p);
}

The demo Successor() function returns null if the current permutation is the last permutation. The demo program defines an IsLast() function as:

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 < order - 1; ++i) {
    if (perm[i] < perm[i + 1])
      return false;
  }
  return true;
}

The last permutation of order n will have the form (n-1), (n-2), . . 0. The IsLast() function does an optional check of the first and last items in the permutation to see if a quick short-circuit return is possible.

The kth Lexicographical Permutation Element Directly
Suppose you want a specific permutation element, for example permutation k = [99] for order n = 5. Because there are only 5! = 120 possible permutations you could start with the initial (0, 1, 2, 3, 4) permutation and then call the Successor() function inside a for-loop with 99 iterations and end up at the desired permutation.

This approach only works for small values of n. Surprisingly, it is possible to write a function that directly returns a specified permutation. The demo program defines an Element() function in Listing 2.

Listing 2: Directly Computing the kth Permutation Element

static int[] Element(BigInteger k, int order)
{
  // kth lexicographical element
  if (k >= Factorial(order))
    throw new Exception("k too large in Element");
  int[] result = new int[order];

  int[] factoradic = new int[order]; // factoradic of k
  for (int j = 1; j <= order; ++j)  // note: skip [0]
  {
    factoradic[order - j] = (int)(k % j);
    k /= j;
  }

  for (int i = 0; i < order; ++i)
    ++factoradic[i];

  result[order - 1] = 1; // last value set to 1
  for (int i = order - 2; i >= 0; --i)
  {
    result[i] = factoradic[i]; 
    for (int j = i + 1; j < order; ++j) 
    {
      if (result[j] >= result[i])
        ++result[j];
    }
  }

  for (int i = 0; i < order; ++i)
    --result[i];

  return result;
}

The Element() function can be called like this:

int order = 5;  // 5! = 120
BigInteger k = BigInteger.Parse("99");
int[] p = Element(k, order);
Console.WriteLine("Permutation [" + k + "] order 5: ");
ShowPerm(p);

The algorithm for the Element() function is one of the most fascinating and beautiful in the field of mathematical combinatorics. The algorithm is based on expressing an integer as a "factoradic," which is a linear combination of Factorial() function values. You can find a detailed explanation of the algorithm in my blog post.

Wrapping Up
The examples in this article use zero-based permutations. This is convenient because in many practical uses of permutations, permutation values map to array indices. In a pure mathematical context, one-based permutations are more common.

A relatively rare concept that's related to permutations are called derangements. A derangement is a permutation where no element is in its original position. For example, if n = 4 there are 4! = 24 permutations, from (0, 1, 2, 3) to (3, 2, 1, 0). For n = 4 there are nine derangements:

1 0 3 2
1 2 3 0
1 3 0 2
2 0 3 1
2 3 0 1
2 3 1 0
3 0 1 2
3 2 0 1
3 2 1 0

The permutation (1, 0, 2, 3) is not a derangement because both 2 and 3 are in their original positions. But (1, 0, 3, 2) is a derangement because none of the four elements are in their original position. In general, about one-third of permutations of order n are also derangements.

• Get Code Download