Thursday, July 28, 2011

Solving Math-related Problems In C++ With STL

Whew, it's been a while since the last post. Lots of things have happened since then; amongst them is my Masters in Computer Science and a new job. The latter forced me to focus less on academic things and more on real world problems (like calculating risks in a distributed environment), so I went back to the basics: C++. I don't really have much time to spend on Haskell anymore (although i still use xmonad as my main window manager :-)).

In the past few months, I have taken up the habit of solving problems from the project euler website. Today, I stumbled across Problem 24, which is pretty simple in principle. Find the 1000000th permutation of the first 10 natural numbers. I usually solve these problems with as much STL as possible because the generic style it forces on you really fits me, so the phrase "lexicographical permutation" struck me as something I have read recently - in an entirely different context. Sure enough, after a bit of poking around, I have found it.

This essentially makes a (brute force) solution three lines of logic in C++, which - let's be honest - is not a common sight. So here's my solution to the problem: