Grind Report 24

Problem 24

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

*WARNING: This contains the solution!*

As usual, this could be solved using a brute force method that would calculate each permutation until the targeted permutation was reached. But since the target is 1 million, that would be a very sad method. Thus, once again, I set out to come up with an algorithm that could calculate any target permutation.

The first and most important thing to know about permutations is that given a set of n characters there are exactly n! (factorial) possible combination. Such as in the example in the question, there are 3 characters and there are 3! = 3 * 2 * 1 = 6 combinations. Since 3 characters can only represent 6 different combinations then if a target permutation such as 10 is requested you know that 4 characters are required, 4! = 24 possible permutations, and consequently you also know that the first digit has to be changed to be able to represent this target permutation.

The 10^th permutation of 0, 1, 2, and 3 is 1230. As you might have noticed by now, the most significant character that needs to be changed is the first one (moving right to left) that has n! / Target >= 1. In our example we have...

1! / 10 = .1
2! / 10 = .2
3! / 10 = .6
4! / 10 = 2.4

So we can see that there are at least 4 characters required to represent this target permutation. Furthermore, using a similar method we can even know which number belongs in the place of the most significant place. This is done by taking the Target / (n – 1)!. Once again in our example we have...

10 / (4 – 1)! = 10 / 6 = 1 r 4

This actually tells us two things. The first thing is that we need to swap the first and second most significant numbers. This is the most significant number and 1 place to the right, which would give us 1023 given that we start with 0123. If this number is larger than 1 it is important to continue to swap the numbers so that besides the place being changed, n, the other numbers need to stay in the lowest lexicographical order possible. Such as if 2 was the number we'd want 2013 and 3 we would want 3012.

The other thing we can pull from this is if we look at the remainder. If we take this remainder, set it as the new target permutation and then decrement n by 1 we can repeat this and once you're done you'll have the original target permutation. Pretty cool huh?

It took me awhile to figure this out but once I understood how the algorithm would work it didn't take long to implement it. Here is my solution. I added comments to help with reading it. :)

#include <iostream>

using std::cout;

const int TARGET = 1000000;
const int CHARCOUNT = 10;

void swap(char &a, char &b);
long factorial(int number);

int main()
{
 //setup array to include 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
 char permutation[CHARCOUNT + 1];
 for (int i = 0; i < CHARCOUNT; ++i)
  permutation[i + 1] = '0' + i;

 //find out how many characters are required to represent the target
 //and store that place so we know where to start
 int place;
 for (place = 1; place < CHARCOUNT + 1; ++place)
 {
  if ((int)(factorial(place) / TARGET))
   break;
 }
 //flip the place around to work with the array indexing
 place = CHARCOUNT - place + 1;
 //set the current target to the original target
 int current = TARGET;
 //this is the main algorithm
 for (;place < CHARCOUNT; ++place)
 {
  //calculate the factorial
  long fact = factorial(CHARCOUNT - place);
  //determine how many places to the right this needs to go
  int index = (current - 1) / fact;
  //store it for later use
  int count = index;
  //this goes over index number of places and continues to swap the numbers
  //until it gets to the current place
  while (index > 0)
  {
   swap(permutation[place + index], permutation[place + index - 1]);
   --index;
  }
  //set the new target for the next iteration of the algorithm
  current -= fact * count;
 }
 //output solution
 for (int i = 1; i <= CHARCOUNT; ++i)
  cout << permutation[i];
}

//swaps two char
void swap(char &a, char &b)
{
 char temp = a;
 a = b;
 b = temp;
}

//returns the factorial of the number (recursive)
inline long factorial(int number)
{
 return (number == 1 ? 1 : number * factorial(number - 1));
}

Oh yeah, I almost forgot to mention. This is fast. Much faster than calculating the 999,999 permutations before it. Also I believe this can calculate any permutation target with any characters, not just numbers - only the top bit of the code needs to be changed. ^^

*saved game*