# Generating the n! permutations in Haskell

Koen Claessen koen@cs.chalmers.se
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).

:-). 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.

```