Recursive function to develop permutations

[Hung Jung Lu]

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