Generating the n! permutations in Haskell
Mon, 10 Jun 2002 09:40:30 +0200 (MET DST)
Shlomi Fish wrote:
| Included below is a Haskell Program I wrote to
| generate the n! permutations of a set of n elements.
Just to also share some programming idiom with you, I often
find myself using the following function:
selections :: [a] -> [(a,[a])]
Given a list xs, it returns a list of pairs of the same
length as xs, where each pair (y,ys) represents one
"selection" from the list xs, i.e. an element from xs (y)
and the rest (ys).
Sadly, it is not a standard Haskell function (it should be!
:-). Here is its implementation:
selections  = 
selections (x:xs) = (x,xs) : [ (y,x:ys) | (y,ys) <- selections xs ]
Using this function, it is really easy to write a
permutations :: [a] -> [[a]]
permutations xs =
[ y : zs
| (y,ys) <- selections xs
, zs <- permutations ys
My apologies if this thread now turns into a "here-is-my-
Chalmers University, Gothenburg, Sweden.