[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))?
> 

Hi Kye,

since your function is calling itself, nothing immediately occurs to me 
that would manage to do what you want in a single function and be 
readable/good style. (Though I could be overlooking something simpler.)

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.

But, 5 minutes of trying to set this up convinced this still new python 
programmer that this will, if workable, be harder to read and maintain 
than the simple of leaving your original function as is and adding this 
function to your program:

def perm_all_but_head(k):
     permed_tail = perm(k[1:])
     for p in permed_tail:
         p = p.insert(0, k[0])
     return permed_tail

Then, instead of calling your perm(), call perm_all_but_head().

Hope that helps,

Brian vdB