# [Haskell-cafe] Re: Generic permutations

Ryan Ingram ryani.spam at gmail.com
Sat Jan 26 17:06:22 EST 2008

```When you say permuations, I think of reorderings of a list, for example:

permutations [1,2,3] =
[ [1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1] ]

Here's an implementation:

-- split [1,2,3] => [
--    ( 1, [2,3] ),
--    ( 2, [1,3] ),
--    ( 3, [1,2] ) ]
split :: [a] -> [(a, [a])]
split [] = error "split: empty list"
split [a] = [(a, [])]
split (a:as) = (a, as) : map prefix (split as)
where prefix (x, xs) = (x, a : xs)

permutations :: [a] -> [[a]]
permutations [] = return []
permutations xs = do
(first, rest) <- split xs
rest' <- permutations rest
return (first : rest')

The problem you solved can be solved much more elegantly:

pms : [a] -> Int -> [[a]]
pms xs n = foldM combine [] (replicate n xs) where
combine rest as = liftM (:rest) as

or, for the unreadable version:
pms xs n = foldM (map . flip (:)) [] \$ replicate n xs

(note that, in the list monad, liftM = map).

-- ryan
```