I have been playing around with some questions on Project Euler over the past couple of days. In general, I like PE for a number of reasons. First, its a site that challenges people to think mathematically, which is always good. It appeals to a couple of my friends who aren’t very strong coders, probably because you dont need a huge coding or algorithms background to attack first 20 problems or so. Hopefully it will lead to them getting more comfortable with brain teaser/coding questions and they can start doing things like Topcoder or the problems on the UVA judge (can’t find a working link right now). Second, not everything requires code to answer, sometimes its just a simple equation evaluation (if you know the right equation) and in general it forces coders to get closer to the math. A lot of times I feel that we lose sight of the fact that we are applied mathematicians and should look at some of the mathematical properties of a problem before we start banging away at the keys or looking for a recurrence relation that we can DP on. Actually, in my Combinatorics class in the fall, I suggested we could solve the lattice path counting problem using a recurrence relation and received a response of “ah, yes that is how a computer scientist would think, but we mathematicians can do better” (it was said in a loving and European way). However, I have some reservations in the fact that most of the problems, at least on the first page, seem to involve simple computations, but adds in difficulty by putting in very large numbers. I guess it’s just a little annoying to have the right algorithm, but have to change data types from “int” to “long long” or just give up on the problem because it requires the use of some big int class.
Anyway, I found one problem that I really did like (problem 24 for those who are interested). The generalized version of the problem is as follows: Given N digits, determine the Kth permutation of the digits (that number K is determined by its position in the lexicographic ordering of all the permutations). So for example, if we were given 1 2 3 and told to find the 4th permutation, we would get 123 as the first, 132 as the second, 213 as the third and 231 as the 4th (the 5th would be 312 and 321 for the 6th). Now, I would like to give this problem at one of our programming competitions and make N semi-large (but small enough such that N! fits with in a 64-bit int). This is one of those problems that has a very obvious brute force solution, but the lack of a small bound on N destroys that approach, thus forcing the programmers to actually think about the problem. The BF approach would be to iterate through every permutation until you hit K (some programmers may not know a standard library call to a next_permutation function, so the problem might be a little bit tougher). Still, it isn’t that hard to come up with a good solution for this problem, so let me talk about that.
One of the nice things about permutation questions is that they usually lend nice recursive solutions, which is my favorite thing to work with. We notice that if we have N elements and we fix the first element, then we have (N-1)! permutations that we can construct. So if K <= (N-1)! then we know that the first element in the solution is the first element in the list. So now it really comes down to finding the Kth permutation of the remaining N-1 digits. If K > (N-1)! , then we know that the first element in the list cannot be the first element in the solution, so we must now switch elements. Since digit D can have (N-1)! permutations constructed with D as the first element, we must find the smallest position i such that i*(N-1)! >= K, and then switch the first element with that ith element. Now its a matter of finding the (K- ((i-1)*(N-1)!))th permutation of the remaining N-1 digits. That expression is a little scary, so let me explain it. Notice that if we had the digits 12345, the first 4! = 24 permutations would all begin with 1. So if we wanted to find the 25th permutation, we realize that 1 cant be the first permutation since it only heads the first 24 permutations, so we switch with the next lexicographic digit, which is 2 in this case. Since we already covered 24 permutations, we really only need to find the 1st permutation with 2 at the beginning, or the first permutation of the digits 1345.
So we modified the permutation number we were looking for by subtracting (i-1)*(N-1)! or the number of permutations that we already ruled out cant be the solution permutation, from the permutation that we are looking for. Again, i is the smallest position such that i*(N-1)! >= K. I am much better at explaining things in person, I swear.
Anyway, if we had put all of this mess together in an algorithm, we get a running time of O(nlgn) if we search for that i cleverly (binary search), which significantly kicks the ass of the brute force O(n!) algorithm. Regardless of this convoluted explanation, its a pretty simple algorithm but it makes you feel nice and special after you are done. I think its a pretty gentle problem to get people to think beyond the obvious, which is something that I strive for with the problems that I write. I have previously done that by beating them over the head with 2 dimensional DP problems, but then that gives people with no algorithms experience no chance at them. This type of problem gives anyone with a knowledge of permutations and basic recursion a decent shot. Since no one reads this blog anyway, I think I should be safe in giving it as a problem in one of this year’s competitions.
