Source Code – https://github.com/ehelin/Algorithms (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 – http://www.bearcave.com/random_hacks/permute.html. 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