Generating the n! permutations in Haskell

[Koen Claessen]

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 function:

  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-
favorite-way-to-do-permutations-discussion".

/Koen.

--
Koen Claessen
http://www.cs.chalmers.se/~koen
Chalmers University, Gothenburg, Sweden.