# Permutations of a list in Haskell

### Using inductive

1. Base case, an empty list has permutations: [[]]

2. Suppose we have all permutations of a list, xs.

3. 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.

4. 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…

5. 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