# Permutations of a list in Haskell

### Using inductive

Base case, an empty list has permutations:

`[[]]`

Suppose we have all permutations of a list, xs.

If we were to add an element x to the head of the list, The permutations would be inclusive of x. Hence we will need to add all possible locations of x to each permutation.

Since 1. is true, then 2. is true, then for any list, we can use step 3 to inductively construct all permutations. E.g. for [1,2,3,4] We construct for: a. [] b. 4:[] c. 3:4:[] and so onâ€¦

Hence we obtain all permutations

```
perms [] = [[]]
perms (x:xs) = [zs | ys <- perms xs -- We generate all the permutations of xs
, zs <- inserts x ys -- With x inserted at all possible locations in each permutation
]
where
inserts :: a -> [a] -> [[a]]
inserts x [] = [[x]]
inserts x (y:ys) = (x:y:ys) : map (y:) (inserts x ys)
```

### Using recursive, helps with equational reasoning

```
perms = foldr step [[]]
where step x xss = concatMap (inserts x) xss
```