Recursive function to develop permutations
Hung Jung Lu
hungjunglu at yahoo.com
Fri Oct 22 07:09:03 CEST 2004
aleaxit at yahoo.com (Alex Martelli) wrote:
>
> def permute(Xs, N):
> if N > 0:
> for x in Xs:
> for sub in permute(Xs, N-1):
> yield [x]+sub
> else:
> yield []
>
> If you do choose an if/else it seems to me things are more readable when
> you arrange them this way (rather than with if N<=0, so the for in the
> else). Matter of tastes, of course.
For an unreadable voodoo version, here is a one-liner:
permute = lambda Xs, N: reduce(lambda r, a: [p + [x] for p in r for x
in Xs], range(N), [[]])
print permute(['red', 'white', 'blue', 'green'], 3)
Actually, we should probably not call it "permute". In combinatorics,
"permutation" usually is reserved for sorting operation on a given
combination. However, I don't have a good name for the described
operation, either. Some people would probably call it "sequential draw
with replacement". It's more like "combination" as in the case of a
"combination lock", or as in "slot-machine combinations". (46 entries
in Google. Zero entry for "slot-machine permutations", quoted search
used.)
For simple permutation on a given list, the voodoo version is:
permutations = lambda x: reduce(lambda r, a: [p[:i] + [a] + p[i:] for
p in r for i in range(len(p)+1)], x[1:], [x[:1]])
print permutations(['a', 'b', 'c'])
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. :)
Hung Jung
More information about the Python-list
mailing list