what the heck is going on here?

[Peter Otten]

markscala at gmail.com wrote:

> I found the following ways to generate permutations on the ASPN:
> Python Cookbook page.
> 
> SLOW (two defs):
> 
> def xcombinations(items,n):
>     if n == 0: yield[]
>     else:
>         for  i in xrange(len(items)):
>             for cc in xcombinations(items[:i]+items[i+1:],n-1):
>                 yield [items[i]]+cc
> 
> def xpermutations(items):
>       return xcombinations(items,len(items))
> 
> FAST:
> 
> def permutations(L):
>     if len(L) <= 1:
>         yield L
>     else:
>         a = [L.pop(0)]
>         for p in permutations(L):
>             for i in range(len(p)+1):
>                 yield p[:i] + a + p[i:]
> 
> The author of the FAST claimed his method was faster, which I wanted
> to test.  I ran the test as follows:
> 
> import time
> name = list('python')
> 
> faster = time.clock()
> for x in range(10000):
>     map(''.join,list(permutations(name)))
> total1 = time.clock() - faster
> print "Total time for faster: ", total1
> 
> xperm_start = time.clock()
> for x in range(10000):
>     map(''.join,list(xpermutations(name)))
> total2 = time.clock() - xperm_start
> print "Total time for xperm: ", total2
> 
> If you run these tests in the order above, FAST takes about a .1
> seconds and slow takes about .17 seconds.  BUT if you reverse the
> order of the test, SLOW takes almost 10 seconds and FAST is about the
> same!  What's more, if you take map, join and list out of the tests
> (there's no reason for them to be there anyway) the order doesn't
> matter any more.  Without map/join/list, SLOW and FAST are almost
> indistinguishable at 10K loops.  What's going on?     ( This was done
> in Python2.4 )

permutations() modifies its argument. Try

items = ["a", "b", "c"]
for p in permutations(items): 
   pass
print items

to see why all measurements after the first pass of permutations() are
bogus. Then modify your code to have permutations() operate on copies of
the 'name' list.

Peter