[Tutor] Permutations?
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