All permutations of a list

[Richard van de Stadt]

Hi,

I was looking for an algorithm to generate all permutations of
a row of numbers. I couldn't find the solution (which I thought
should be recursive) myself and looked on the internet, found
a non-recursive C program by one Frank Ruskey, and translated
it to python in a few minutes. It's 40 lines of code.

Then a collegue of mine impressed me with a recursive program
in the functional language Miranda/Amanda:

ins a []     = [[a]]
ins a (x:xs) = (a:x:xs) : map (x:) (ins a xs)

perms []     = [[]]
perms (x:xs) = concat (map (ins x) (perms xs))

'ins a xs' returns a list of all possible extensions of
the list xs by inserting element a.
'perms xs' returns the list of all possible permutations
of the list xs.
'concat' joins lists.

Is such an elegant recursive solution possible in Python?

Richard.