what the heck is going on here?

[markscala at gmail.com]

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 )