Producing permutations, part four

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.


8 thoughts on “Producing permutations, part four

  1. If you only perform the range check in the base case you get the same result without the cost of calculating the factorial.

    The recursion happens at the start of the function so you still bail out in the exceptional case before doing any real work.

  2. Nice work as always. Just a couple of questions/comments:

    Is it really appropriate to call the method “NthPermutation”, when the parameter which describes the permutation number is called “m”, and the parameter called “n” describes the size of the set?

    If 0 <= m < n! and n == 0, then m must be zero by definition. There's no point checking both "n == 0" and "m == 0" in the simple case.

    • Oh good heavens, I never even thought of that. You’re absolutely right; I’ve made a candy machine interface. My bad. I’ll fix it over the weekend.

      (A “candy machine interface” is named after the candy machines at Microsoft where you could easily confuse the price with the item number and thereby “pass the wrong data” into the candy machine and get the wrong candy out. The term is due to Steve Maguire.)

  3. Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1344

  4. Shouldn’t
    BigInteger group = m / n; // What block are we in?
    BigInteger group = m / Factorial(n – 1); // What block are we in?

  5. Great article as always. I have a couple of queries…

    In the range check, shouldn’t “Factorial(n)” be “Factorial(size)”?

    In this observation: “index is always smaller than size”, shouldn’t that be “Factorial(size)”?

    • #1: looks like Eric missed that one when he fixed the candy-machine interface. (The parameters were originally called “m” and “n” instead of “size” and “index”.)

      #2: The observation reads “index is always smaller than size!.” The exclamation mark on the end is the usual mathematical representation of a factorial. It’s slightly confusing because we might expect the exclamation mark to indicate the end of the sentence, but that’s covered by the full-stop following it.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s