[Tutor] Permutations? (original) (raw)

Brian van den Broek bvande at po-box.mcgill.ca
Sun Jul 25 12:27:58 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))? ________________________ 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

More information about the Tutor mailing list