[Tutor] Permutations?

[Brian van den Broek]

Hee-Seng Kye said unto the world upon 25/07/2004 03:40:
> def perm(k): # Compute the list of all permutations of k if len(k) <=
> 1: return [k] r = [] for i in range(len(k)): s =  k[:i] + k[i+1:] p =
> perm(s) for x in p: r.append(k[i:i+1] + x) return r
> 
> Could someone tell me how I can modify the above function so that it 
> produces a list of permutations of k that only begins on k[0]?
> 
> If k = [0,1,2,3], I want to modify perm(k) so that it only produces 
> [[0,1,2,3], [0,1,3,2], [0,2,1,3], [0,2,3,1], [0,3,1,2], [0,3,2,1]].
> 
> I could produce the list of ALL permutations of k and then delete the 
> ones which don't begin with k[0], but for a large list, this could 
> really slow things down.  I was thinking of algorithm that computes
> only the ones I want.
> 
> I would appreciate anyone's suggestion.  Thanks.
> 
> Best, Kye
> 
> p.s. By the way, does anyone have any idea if it would drive my
> computer (667 MHz and 512MB RAM) nuts to perm(range(12))?
> 
> _______________________________________________ Tutor maillist  -
> Tutor at python.org http://mail.python.org/mailman/listinfo/tutor
> 

Hi,

I just realized I should have said the following a bit better:

> I think you should be able to do this all in a single function by
> tracking on what level of the recursive call you are at. You could do
> this with a variable in the global namespace. This would be defined
> outside the function or within it with a global statement. (This last
> way also would need some try/except logic to prevent reinitializing
> your tracker each time you call the function.) The idea then would be
> to strip of the first element only on the first level of perm() calling
> and reattach it to all permutations before returning out of that level.

In thinking about how to explain my intent better, I realized why I had 
hit a snag in my attempt to code up the approach earlier. So, code rather 
than English ;-)

def perm2(k):
     # Compute the list of all permutations of k that leave k[0] in place
     try:
         track = track + 1   # Will raise exception first time through
     except NameError:
         track = 0           # Set to 0 only on first pass
         global track
     if len(k) <= 1:
         track = track - 1
         return [k]
     r = []
     if track == 0:
         first = k[0]
         k = k[1:]
     for i in range(len(k)):
         s =  k[:i] + k[i+1:]
         p = perm2(s)
         for x in p:
             r.append(k[i:i+1] + x)
     if track == 0:
         for p in r:
             p = p.insert(0, first)
     track = track - 1
     return r

But for readability and keeping the global namespace clean{*}, I like my 
first reply's solution better. Plus on long inputs, it should run faster 
as skipping the try/except blocks of this version.

{*} The global is a potential problem because you have to be sure there is 
no track object already in the namespace the function can see when called. 
It's asking for trouble to use one when you can avoid it.

Best,

brian vdB