TGIMBA Automation – Permutation Algorithm Revisited

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

TenCharacterResult2

Eleven Character Result

ElevenCharacterResult

Stay tuned!

References

1) http://www.bearcave.com/random_hacks/permute.html
2) http://www.purebasic.fr/english/viewtopic.php?t=37012

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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