# Permutations in Haskell or "I feel old ..."

I was actually looking for someone who have made a simulation of the gravitational force between particles, but instead I came across another topic concerning haskell.

The author had tried to grok haskell a few times and was stuck again on his third attempt. He had a problem with understanding an implementation of calculating all possible permutations of a list of items.

His friend had given him one implementation which was difficult to grasp.

``````permute :: [a] -> [[a]]
permute = foldr (concatMap . ins) [[]]
where ins x []     = [[x]]
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]
``````

So I thought I would try implement a variant of `permute`. To understand this explanation it is useful to know basic haskell concepts including lists, functions and pattern matching and list comprehension.

First I tried some examples of permute on paper.

``````                    [a]
[a,b]                  [b,a]              -- insert b in [a]
[c,a,b][a,c,b][a,b,c]  [c,b,a][b,c,a][b,a,c]      -- insert c in [a,b] and [b,a]
``````

So for one item you are done. For two items you can switch the order to get the second permutation. For three items you can insert the third item (`c`) at three location in both of the permutations of the previous set of two permutations. This is actually what you do when going from one to two elements as well i.e. inserting `b` before and after `a`.

So it would be useful to have a function insert (`ins`) which insert an item at all possible locations in a list and return all these lists in a list. So how do you do that. Imagine the following function. We have a single item x and a list where the first item is `y` (head) and the rest of the list is `ys` (tail).

``````ins x (y:ys)
``````

One list where `x` is inserted in `(y:ys)` is `x:y:ys` i.e. `x` inserted first in the list `y:ys`. `ins x ys` is `x` inserted in `ys` at all possible locations. Lets take a concrete example.

``````x = 'c'
(y:ys) = ['a','b']    -- y = 'a' and ys = ['b']
``````

In this case `x:y:ys` would compute to the following.

``````x:y:ys        --  ['c','a','b']
ins x ys      --  ins 'c' ['b'] ==> [['c','b'],['b','c']]
``````

So if you take `y` in front of each of `ins x ys` results you will have the rest of the results from `ins x (y:ys)`. This can be expressed as list comprehension.

``````[y:res | res <- ins x ys]
``````

So `ins` can really be implemented by taking `x:y:ys` as a first result and then insert `y` in front of the recursive result from `ins x ys` i.e. `[y:res | res <- ins x ys]`. The only thing to do is to define a base case for the recursion to finish. Insert `x` in a empty list is the most basic case which is trivially implemented.

``````ins x [] = [[x]]
``````

So now we can understand why `ins` can be implemented as follows.

``````ins x []     = [[x]]
ins x (y:ys) = (x:y:ys):[y:res | res <- ins x ys]
``````

From the examples of permutations above I would implement `permute` as follows. I also added a small `main` to test the function.

``````permute :: [a] -> [[a]]
permute []       = [[]]
permute (x:[])   = [[x]]
permute (x:y:[]) = [[x,y],[y,x]]
permute (x:ys)   = concatMap (ins x) (permute ys)

main = do print \$ permute ['a','b','c']
``````

`concatMap` applies `ins x` on each list element of `permute ys` and concatenates its results. As `ins x` on a list produce a list of lists the concatenation of `concatMap` is used to collect the results as a single list.

``````runhaskell Permute.hs
["abc","bac","bca","acb","cab","cba"]
``````

Because `ins` can handle the case where `ys` is empty in `permute ys`, the cases where the list parameter to `permute` has one or two elements is not required for the recursion to finalize. The simplified solution is as follows. `ins` is also implemented as a sub-function of `permute`.

``````permute :: [a] -> [[a]]
permute []       = [[]]
permute (x:ys)   = concatMap (ins x) (permute ys) where
ins x []     = [[x]]
ins x (y:ys) = (x:y:ys):[y:res | res <- ins x ys]

main = do print \$ permute ['a','b','c']
``````

The original solution where `foldr` is used, instead of a recursive call to `permute`, is bit more difficult to grasp, but equivalent.