permutations

# Permutations

1. define the function `map f l` that applies the function `f` to each element of the list `l`

`map : ('a -> 'b) -> 'a list -> 'b list`

2. Define the function `shuffle x l` that inserts the element `x` at each position inside the list `l`. For instance, `shuffle 1 [2;3]` evaluates to [ [1;2;3]; [2;1;3]; [2;3;1] ]

`shuffle : 'a -> 'a list -> 'a list list`

3. define the function `flatten l` that transforms a list of lists of elements of type T into a list of elements of type T. For instance, `flatten [ [1;2]; [3;4;5] ]` evaluates to `[1;2;3;4;5]`.

`flatten : 'a list list -> 'a list`

4. Define the function `perm l` that evaluates to the list of all the permutations of the elements of the list `l`. For instance, `perm [1;2;3]` evaluates to `[ [1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1] ]`.

`perm : 'a list -> 'a list list`

## Solution

```let rec map f l = match l with
[] -> []
| x::xl -> f(x) :: map f xl;;

let rec shuffle y l = match l with
[] -> [[y]]
| x::xl -> (y::x::xl) :: (map (fun l -> x::l) (shuffle y xl));;

let rec flatten ll = match ll with
[] -> []
| x::xll -> x @ (flatten xll);;

let rec perm l = match l with
[] -> [[]]
| x::xl -> flatten (map (shuffle x) (perm xl));;``` 