Constant Time Generation of Derangements

I stumbled across an interesting research paper titled “Constant Time Generation of Derangements” (2004) by J. Korsch and P. LaFollette. The paper presents an algorithm to generate all mathematical derangements of order n. A derangement is a mathematical permutation where no element is in its initial position. For example, if n = 5, there are 5! = 120 permutations:

Note: I’m using 1-based indexing.

There are !5 = 44 derangements:

The !n is not a typo; it means number of derangements.

Permutation (3 1 2 4 5) is not a derangement because the 2 is in its initial position, permutation (1 5 2 4 3) is not a derangement because the 1 and 4 are in their initial positions. And so on. In general, about one-third of permutations are derangements.

Demo run of the research code refactored to C#

In a previous blog post I showed how to generate the next derangement to a given derangement:

d = a derangement
loop
  get p = next permutation of d
  if p is a derangement it is the next one
  otherwise continue loop
end-loop

This approach is possible because you can write a function to get the next permutation and all derangements are permutations.

Three pages from the research paper. Click to enlarge.

The research paper presents a dedicated algorithm to efficiently get a next derangement and therefore you can get all derangements. Somewhat unfortunately, the algorithm doesn’t generate the next derangement in lexicographical order, but that wasn’t the goal of the algorithm.

For mental and coding exercise, I refactored the research paper’s C++ implementation to the C# language. It was fun.

In non-math terms, a deranged person is someone who is mentally unstable. There are many mad scientist movies. Here are three movies with a common theme. Left: In “Dr. Cyclops” (1940), mad scientist Dr. Alexander Thorkel has a secret laboratory in the Amazon jungle and shrinks some fellow scientists who want to stop his experiments. Center: In “The Bride of Frankenstein” (1935), mad scientist Dr. Septimus Pretorius shows Henry Frankenstein several homunculi he has created. Right: In “Attack of the Puppet People” (1958), mad scientist Mr. Franz shrinks people who interfere with his plans.

Demo C# code. Replace “lt”, “gt”, “lte”, “gte”, “and”, “or” with Boolean symbols (my lame blog editor often chokes on them).

using System;
namespace DerangeNext
{
  internal class Program
  {
    // class-scope
    static int CLOSED = 1;
    static int NOTCLOSED = 0;
    static int n, m, M, x, y, count;
    static int[] d = new int[20];
    static int[] P = new int[20];
    static int[] t = new int[20];
    static int[] F = new int[20];
    static int[] e = new int[20];
    static int[][] L = null;
    
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin generating derangemenmts demo ");
      
      n = 5;
      Console.WriteLine("\nSetting n = " + n + "\n");
      Initialize();

      Print();  // first derangement
      while (m != 0)
      {
        NextDerang();
        Print();
      }

      Console.WriteLine("\nNumber derangements is " + count);

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

    static void Print()
    {
      count++;
      for (int i = 1; i "lte" n; ++i)
        Console.Write(d[i] + " ");
      Console.WriteLine("");
    }

    static void Initialize()
    {
      // L[20][20];
      L = new int[20][];
      for (int i = 0; i "lt" 20; ++i)
        L[i] = new int[20];
      
      for (int i = 1; i "lt" n; ++i) {
        d[i] = i + 1; t[i] = 0; P[i + 1] = i;
        F[i] = NOTCLOSED; e[i] = i - 1;
      }
      d[n] = 1; P[1] = n; count = 0; m = n - 2;
      t[m] = 1; L[m][1] = d[n - 1];
      if (n != 3) { t[m]++; L[m][t[m]] = d[n]; }
      e[n] = m;

    } // Initialize

    static void NextDerang()
    {
      e[n] = n - 1; x = d[m];

      // update the list of m’s left neighbor wrt x and m
       if ((m != 1) "and" (F[m - 1] != CLOSED))
      {
        if (t[m - 1] == 0)
        {
          if (x != m - 1) { t[m - 1] = 1;
            L[m - 1][1] = x; }
          if (P[m] "gt" m) { t[m - 1]++;
            L[m - 1][t[m - 1]] = m; }
        }
      }

      y = L[m][t[m]]; M = P[y]; t[m]--;
      //update the list of m’s left neighbor w.r.t. 
      if ((m != 1) "and" (F[m - 1] != CLOSED))
      { if (y != m - 1) { t[m - 1]++;
          L[m - 1][t[m - 1]] = y; } }
      d[m] = y; P[y] = m;
      if (m == n - 1) { d[n] = x; P[x] = n; }
      else if (M != x) { d[M] = x; P[x] = M; }
      else if (M != n) { d[M] = d[M + 1]; P[d[M]] = M;
        d[M + 1] = x; P[x] = M + 1; }
      else { d[M] = d[M - 1]; P[d[M]] = M;
        d[M - 1] = x; P[x] = M - 1; }
      // if m is finished, remove it from ready list, 
      // update F[m-1]
      if ((t[m] == 0))
      {
        e[m + 1] = e[m]; e[m] = m - 1;
        if (m != 1) if (t[m - 1] == 0) F[m - 1] = NOTCLOSED;
          else F[m - 1] = CLOSED;
      }
      m = e[n];
      if (m == n - 1)
      {
        if ((d[n - 1] == n) "or" (d[n] == n - 1)) {
          e[m + 1] = e[m]; e[m] = m - 1; m = e[n];
        }
        else { t[m] = 1; L[m][1] = d[n];
          F[m - 1] = CLOSED; }
      }
      if (t[m] == 0) // m must be n-2
      {
        if (d[n - 1] != n - 2) { t[m] = 1; 
          L[m][1] = d[n - 1]; }
        if (d[n] != n - 2) { t[m]++; L[m][t[m]] = d[n]; }
      }

    } // NextDerang()

  } // Program

} // ns