Recursive function to develop permutations

[Steve Goldman]

Hi,

I am trying to come up with a way to develop all n-length permutations of a
given list of values. The short function below seems to work, but I can't
help thinking there's a better way. Not being a computer scientist, I find
recursive functions to be frightening and unnatural. I'd appreciate if
anyone can tell me the pythonic idiom to accomplish this.

Thanks for your help,

Steve Goldman

###START CODE###

def permute(list,n, initialize=True ):
"""A recursive function that returns a list of all length n ordered
permutations of "list", length k."""
if initialize:
global permutation, permutation_lis t
permutation=[] #This list holds the individual permutations. It
is built one element at a time
permutation_lis t=[] #This list is the list that will contain all
the permutations
n=n-1 #This counts down for each element of the permutation. It is a
local variable,
#so each subsequent function call has n reduced by one
for e in list:
permutation.app end(e)
if n>0: #that is,the permutation needs additional elements
permute(list,n, False)
else: # the permutation is length n
permutation_lis t.append(permut ation[:]) #store the completed
permutation
permutation.pop (-1) # knock off the last value and go to the next
element in "list"
return permutation_lis t
if __name__=='__ma in__':
list=['red','white',' blue','green']
print permute(list,3)

[Hung Jung Lu]

hu********@yaho o.com (Hung Jung Lu) wrote:

No if/else statements. No explicit recursion. And it works for
zero-length lists as well. Now, if someone could do the general P(n,
k) and C(n, k) versions, I'd appreciate it. :)

Well, here they are: (for functional people, basically I used
tail-call and parameter list to emulate looping variables... standard
trick, nothing new. The formulas might be further simplified?)

permutations = lambda Xs, k: [p[0] for p in reduce(lambda r, i:
[[x+[y[i]], y[:i]+y[i+1:]] for (x, y) in r for i in range(len(y))],
range(k), [[[], Xs]])]

combinations = lambda Xs, k: [p[0] for p in reduce(lambda r, i:
[[x+[y[i]], y[i+1:]] for (x, y) in r for i in range(len(y))],
range(k), [[[], Xs]])]

slot_machine_co mbinations = lambda Xs, k: [p[0] for p in reduce(lambda
r, i: [[x+[y[i]], y] for (x, y) in r for i in range(len(y))],
range(k), [[[], Xs]])]

sample = ['a', 'b', 'c', 'd']
print permutations(sa mple, 2)
print combinations(sa mple, 2)
print slot_machine_co mbinations(samp le, 2)

The three formulas only differ in the treatment of the y[] lists in
looping. That part can be parametrized into separate lambdas if so
desired.

permutations: y --> y[:i] + y[i+1:]
combinations: y --> y[i+1:]
slot_machine_co mbinations: y --> y

Hung Jung