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:

int ints[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for (int i = 1; i < 1000000; ++i) std::next_permutation(ints, ints+10);
for (int i = 0; i < 10; ++i) std::cout << ints[i];
I just wanted to share this little piece of code since I find it beautiful and self-explanatory and that can not often be said about C++ source code. I might share more of these when I get some time and motivation, so stay tuned ;-)

1 comment:

  1. Geez, I totally forgot that you have a blog until this post showed up in my rss reader...

    Anyway, In Haskell the solution would be way more beautiful.