TGIMBA Automation – Permutation Algorithm Revisited

Source Code – (get the commit closest to the date of this blog)

Well, I didn’t get very far with increasing the permutation algorithm to 50 like I had hoped in its current form.  First, I had an out of memory exception.  When I removed the stored permutations, I was able to add eleven characters whose factorial is around 39 million.  However, when I added the test for 12, it kept taking a while.  So, I checked the factorial and it was half a billion (ish).  When I did the factorial for 50, it was…well, let’s just say really, really large (the scientific notation was 10X64).  Clearly, I am going to have to change this and won’t be able to do it as I had planned.

On an interesting note, the 11 character automated test ran in about a minute or two.  The 12 character one ran in about 18 minutes.  OK, score one for not doing the brute force way.  But like I said, I think I will retain this better having tried it on my own first.

So, a random google search took me to a blog entry by ‘Ian L. Kaplan’ here –  I picked the University of Exeter and Alexander Bogomolyn algorithms for comparison to mine.  The results are humbling (see below).  For ten characters, mine was roughly 8 seconds behind.  For 11, over a minute.  Part of the reason (I think) is because I am doing some sorting and using lists vs just one int array.  I will revisit this in a future blog post if I can get my homegrown version to work.  After reviewing the University of Exeter algorithm, I think the one I hacked put together resembles it a lot.  However, instead of using recursion, I increment and keep moving the operations accordingly.  I also noticed that Alexander Bogomoyn’s algorithm starts out with all 0’s.  This was confusing at first until I set a debug line.

I am going to set them up to run for 50 characters (will take a while) and this will be where I start tweaking and deciding how best to work into the TGIMBA automation.

Ten Character Result


Eleven Character Result


Stay tuned!




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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s