Generating the n! permutations in Haskell

Koen Claessen
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 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-


Koen Claessen
Chalmers University, Gothenburg, Sweden.