Generating the kth Lexicographical Element of a Permutation Using the Factoradic

Suppose you are working with mathematical permutations of order n = 3. There are 3! = 6 different permutation elements. In lexicographical order they are:

[0] 0 1 2
[1] 0 2 1
[2] 1 0 2
[3] 1 2 0
[4] 2 0 1
[5] 2 1 0

Note: I use 0-based indexing.

Several years ago I learned about a neat technique from Peter Cameron of Queen Mary, University of London. He suggested that the factoradic of a number can be used to generate the kth permutation of order n. He was not sure where the term “factoradic” originated so I use it too. I published an article in the old Microsoft MSDN Magazine but MSDN has been vaporized into Internet ether. I summarize that old article in this blog post.

If you want just element [4] you could start with (0 1 2) and assuming you have a Successor() function, loop 4 times to get to (2 0 1). It turns out that writing a Successor() function for permutations is a bit tricky but feasible. However, because the number of permutations for order n become astronomically large for even moderate sized values of n, the iteration approach won’t work except for small values of n.

It turns out that there’s a clever way to directly generate permutation element [k] using an old idea called the factoradic. The essence of the algorithm is to take k, compute its “factoradic”, and then use that to compute the permutation.

You can think of a factoradic as an alternate representation of an integer. Consider the integer 859. It can be represented as

859 = (8 * 100) + (5 * 10) + (9 * 1)

Or another way of looking at it is as based on a fixed radix (base) of powers of 10:

859 = (8 * 10^2) + (5 * 10^1) + (9 * 10^0)

In short, any number can be uniquely represented as a linear combination of powers of 10. The factoradic of an integer is its representation based on a variable base corresponding to the values of n factorial. It turns out that any integer k can be uniquely represented in the form

k = (a0 * 1!) + (a1 * 2!) + (a2 * 3!) + (a3 * 4!) + . . .
  = (a0 * 1) + (a1 * 2) + (a2 * 6) + (a3 * 24) + . . .

For example, the integer 859 can be represented as

 
 = (1 * 1!) + (0 * 2!) + (3 * 3!) + (0 * 4!) + (1 * 5!) + (1 * 6!)
 = (1 * 1) + (3 * 6) + (1 * 120) + (1 * 720)

So 859 in factoradic form is { 1 1 0 3 0 1 } where the right-most digit is the value of the 1!s. It will be useful to append a trailing 0 onto the right end of all factoradics so { 1 1 0 3 0 1 0 } is the final form for 859.

Furthermore, it turns out that there is a one-to-one mapping between the factoradic of an integer k and the kth permutation of order n, meaning that each factoradic uniquely determines a permutation. To illustrate this, the following table shows the values of k, the factoradic of k, and the kth permutation for order n=4.

 k     factoradic    permutation
--------------------------------
[ 0]   { 0 0 0 0 }   ( 0 1 2 3 )
[ 1]   { 0 0 1 0 }   ( 0 1 3 2 )
[ 2]   { 0 1 0 0 }   ( 0 2 1 3 )
[ 3]   { 0 1 1 0 }   ( 0 2 3 1 )
[ 4]   { 0 2 0 0 }   ( 0 3 1 2 )
[ 5]   { 0 2 1 0 }   ( 0 3 2 1 )
[ 6]   { 1 0 0 0 }   ( 1 0 2 3 )
[ 7]   { 1 0 1 0 }   ( 1 0 3 2 )
[ 8]   { 1 1 0 0 }   ( 1 2 0 3 )
[ 9]   { 1 1 1 0 }   ( 1 2 3 0 )
[10]   { 1 2 0 0 }   ( 1 3 0 2 )
[11]   { 1 2 1 0 }   ( 1 3 2 0 )
[12]   { 2 0 0 0 }   ( 2 0 1 3 )
[13]   { 2 0 1 0 }   ( 2 0 3 1 )
[14]   { 2 1 0 0 }   ( 2 1 0 3 )
[15]   { 2 1 1 0 }   ( 2 1 3 0 )
[16]   { 2 2 0 0 }   ( 2 3 0 1 )
[17]   { 2 2 1 0 }   ( 2 3 1 0 )
[18]   { 3 0 0 0 }   ( 3 0 1 2 )
[19]   { 3 0 1 0 }   ( 3 0 2 1 )
[20]   { 3 1 0 0 }   ( 3 1 0 2 )
[21]   { 3 1 1 0 }   ( 3 1 2 0 )
[22]   { 3 2 0 0 }   ( 3 2 0 1 )
[23]   { 3 2 1 0 }   ( 3 2 1 0 )

For example, for k = 5, the factoradic is { 0 2 1 0 } = (0 * 3!) + (2 * 2!) + (1 * 1!) + 0 and the [5] permutation of order 4 is ( 0 3 2 1 ).

The clever and efficient way to compute the kth permutation of order n is to first find the factoradic of k and then to generate the corresponding permutation from the factoradic.

The trickiest part of the algorithm is the computation of the permutation that corresponds to the factoradic. Here’s an example that shows how the algorithm converts the factoradic { 1 2 3 2 1 1 0 } into its corresponding permutation of order n=7 which is ( 1 3 5 4 2 6 0 ).

First create a temp[] array and copy into it the factoradic values incremented by 1:

[ 2 3 4 3 2 2 1 ]

The result[] permutation array is seeded with a 1 value in the right-most cell:

[ ? ? ? ? ? ? 1 ] 

Now starting with the second value from the right-most value of the factoradic (skipping over the right-most because it will always be 1 since it came from the padded 0 value), add it to the result[] array:

[ ? ? ? ? ? 2 1 ]

Now the algorithm scans through all the values to the right of the new value and increments by 1 all values that are greater than or equal to the new value. Continuing this process generates:

[ ? ? ? ? 2 3 1 ]
[ ? ? ? 3 2 4 1 ]
[ ? ? 4 3 2 5 1 ]
[ ? 3 5 4 2 6 1 ]
[ 2 4 6 5 3 7 1 ]

Last, the algorithm traverses the result[] array and decrements all values by 1 to put the resulting permutation in 0-based form:

( 1 3 5 4 2 6 0 )

To summarize, if you want to generate the kth permutation of order n, first compute the factoradic of k, and then use that result to compute the corresponding permutation. The example above started with k = 1,047 and then computed its factoradic = { 1 2 3 2 1 1 0 } and then computed the permutation ( 1 3 5 4 2 6 0 ). So the permutation [1047] of order 7 is ( 1 3 5 4 2 6 0 ).

Here is C# code that implements the algorithm, where a permutation is represented as an array of int values. The implementation uses the BigInteger type because Factorial() can be huge.

Replace “lt”, “gt”, “lte”, “gte” with Boolean operator symbols (my lame blog editor chokes on symbols).

using System; 
using System.Numerics;
namespace Permutations // classic style template
{
  internal class PermutationsProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin factoradic demo ");

      int n = 7;  // order
      BigInteger k = BigInteger.Parse("1047");  // k could be huge
      int[] perm = Element(k, n);
      Console.WriteLine("\nPermutation[" + k + "] of order 7: ");
      ShowPerm(perm);

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

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

    static int[] Element(BigInteger k, int order)
    {
      if (k "gte" 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 "lte" order; ++j)  // note: skip [0]
      {
        factoradic[order - j] = (int)(k % j);  // always an int
        k /= j;
      }

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

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

      for (int i = 0; i "lt" order; ++i) // make 0-based
        --result[i];

      return result;
    }

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

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

  } // Program
} // ns