Last time on FAIC I implemented a short algorithm that produces a sequence containing every permutation of a given size, such that the sequence is a Hamiltonian tour of the vertices of the n-dimensional permutohedron. That is, the shape you get when you make each vertex have the coordinates of a permutation, and an edge connects two permutations that differ only by a swap of adjacent items.

Since we have an algorithm that produces the same order every time, we can number each ordering; it is convenient to do so starting with zero and going to n!-1. What I’d like is an algorithm which given size, the number of items in the permutation, and index, an integer between zero and size!-1, gives back the indexth permutation of length size, without having to calculate all of them.

The solution follows very nicely from the way we characterized the problem of obtaining the whole sequence in the first place. Recall that to obtain the sequence we recursively compute the set of (size-1)! permutations of length size-1 in order, and then make a “block” of size modifications to each. To figure out what the indexth permutation with size elements is we first obtain the permutation of length size-1 we’re inserting into and then figure out which of size possible modifications to make. That is, we’re working out first, which “block” are we in, second, is the insertion point moving forwards or backwards in that block, and third, exactly where the insertion point is.

The only slightly tricky bit that middle bit: knowing what “direction” the location of the new element is “moving” during the insert: it is moving “backwards” in the first (counting from zero) “block” and “forwards” in the second, “backwards” in the third… so we can work out the direction by knowing whether the sub-permutation we’re inserting into was odd or even.

The index can be extremely large of course; factorials grow quickly. 13! is too large to fit into an int and 21! is too large to fit into a long, so let’s use BigInteger from System.Numerics. For range checking purposes we’ll need a helper method to compute factorials:

private static BigInteger Factorial(int x)
{
  BigInteger result = 1;
  for (int i = 2 ; i <= x ; ++i)
    result *= i;
  return result;       
}

And again we’ll follow the same structure as every recursive method: solve the base case if you can. The base case is the first permutation (indexed by zero) of zero elements; you can’t get more basic than that! If we don’t have a base case problem then we reduce the problem to a smaller problem, solve it recursively, and then modify the solution to solve the larger problem:

public static Permutation NthPermutation(int size, BigInteger index)
{
  if (index < 0 || index >= Factorial(size))
    throw new ArgumentOutOfRangeException("index");
  if (size == 0) // index must be zero since it is smaller than 0!
    return Empty;
  BigInteger group = index / size; // What block are we in?
  Permutation permutation = NthPermutation(size - 1, group);
  bool forwards = group % 2 != 0; // Forwards or backwards?
  int insert = (int) (index % size); // Where are we making the insert?                      
  return new Permutation(
    permutation.InsertAt(forwards ? insert : size - insert - 1, size - 1));
}

And there you go.

Were I implementing this in a public library, for performance reasons I would make an outer method that checks the range that simply calls an inner method that does not. Checking the index every time is unnecessary; once it passes the first test, every subsequent test will pass. Or, see the comments for a clever way to avoid this.

We have good reason to believe that this is not an infinite recursion; in fact we recurse only size times, since size gets smaller by one every time. We also know that index goes to zero because index is always smaller than size!.

Next time on FAIC we’ll look at an interesting way to represent the index.