[Tutor] Permutations? (original) (raw)

Brian van den Broek bvande at po-box.mcgill.ca
Sun Jul 25 11:37:32 CEST 2004

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

More information about the Tutor mailing list