tag:blogger.com,1999:blog-4150232295397368657.post4000225194903299137..comments2012-10-18T16:48:23.835-04:30Comments on /random/thoughts: Permutationsnicolaslarahttp://www.blogger.com/profile/15167966852380794888noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-4150232295397368657.post-31491204507451213392009-02-02T15:54:00.000-04:302009-02-02T15:54:00.000-04:30I wrote a series of related posts last year that y...I wrote a series of related posts last year that you may find interesting. <BR/><BR/>http://antimatroid.wordpress.com/2008/06/29/one-tree-many-possibilities/<BR/><BR/>http://antimatroid.wordpress.com/2008/07/06/one-tree-many-possibilities-part-2/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4150232295397368657.post-51485154144876963742009-02-01T11:43:00.000-04:302009-02-01T11:43:00.000-04:30@Anonymous: Thanks for the comment! I fixed it.@Anonymous: <BR/> Thanks for the comment! I fixed it.nicolaslarahttps://www.blogger.com/profile/15167966852380794888noreply@blogger.comtag:blogger.com,1999:blog-4150232295397368657.post-83104139211833860812009-02-01T11:37:00.000-04:302009-02-01T11:37:00.000-04:30@Default:your computer is probably faster than min...@Default:<BR/>your computer is probably faster than mine. <BR/><BR/>I ran python's implementation on my machine and got 0m3.591s for generating and printing which compares to 0m5.615s for heap (the fastest) and 0m6.233s for permutate (the slowest) considering they're written in pure python. And only for the generation pythons implementation ran in 0m0.492 while heap ran un 0m2.192s and permutate in 0m2.515s. Clearly most of python's permutation algorithm is in the printing.<BR/><BR/>A more fair comparison would be to compare the python implementation of python's permutation algorithm: in my machine it took 0m8.867s to generate and print and 0m5.088s just to generate. Still, python's is a superior algorithm because it can permutate arrays of elements of arbitrary size without swapping them around.nicolaslarahttps://www.blogger.com/profile/15167966852380794888noreply@blogger.comtag:blogger.com,1999:blog-4150232295397368657.post-16728436076184841522009-02-01T08:52:00.000-04:302009-02-01T08:52:00.000-04:30salty-horse I know ;) I keep a copy of python trun...salty-horse I know ;) I keep a copy of python trunk updated in my desktop.<BR/><BR/>(my test program called list over permutation to generate the list)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4150232295397368657.post-22736979859407482402009-02-01T08:29:00.000-04:302009-02-01T08:29:00.000-04:30Default, it's unfair to compare Python's implement...Default, it's unfair to compare Python's implementation to these since it's written in C (and uses "yield" which saves some time and memory).<BR/><BR/>The algorithm itself can return permutations of sizes smaller than the length of the array.<BR/><BR/>Besides that, it is similar to the third recursive algorithm, with a nice approach to the permutation on the smaller array. (Rotating them before replacing elements)<BR/><BR/>It also uses a nice trick that can be used to overcome the "total order, unique elements" constraint of Dijkstra's algorithm.<BR/>range(len(a)) is permuted and the indices are used to "order" the elements in a:<BR/><BR/>for indices in permute(a):<BR/> print [a[i] for i in indices]<BR/><BR/>Due to that trick, though, lists with repeated elements will produce duplicate permutations.<BR/><BR/>The code is here:<BR/>http://svn.python.org/view/python/trunk/Modules/itertoolsmodule.c?view=markupAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-4150232295397368657.post-87605763021442409962009-02-01T07:24:00.000-04:302009-02-01T07:24:00.000-04:30Took 0m0.433s to generate permutations of nine ele...Took 0m0.433s to generate permutations of nine elements and 0m2.351s to generate and print.<BR/><BR/>(MBP 2.16 python 2.6)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4150232295397368657.post-37137298825113236002009-02-01T07:19:00.000-04:302009-02-01T07:19:00.000-04:30Since you are using python:#!/usr/bin/env python2....Since you are using python:<BR/><BR/>#!/usr/bin/env python2.6<BR/><BR/>from itertools import permutations<BR/><BR/>for permutation in permutations([1, 2, 3, 4]):<BR/> print(permutation)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4150232295397368657.post-44531774914747888142009-02-01T07:13:00.000-04:302009-02-01T07:13:00.000-04:30A niggle, but the phrase "the exponential nature o...A niggle, but the phrase "the exponential nature of the problem" is technically incorrect - n! is not Θ(1)^nAnonymousnoreply@blogger.com