Computing permutations of a list in F#
Tags: fsharp, recursion, algorithms
Published: 2020-06-05 20:52:56

TL;DR, here is the final code.
```fsharp
let permute list =
  let rec inserts e = function
    | [] -> [[e]]
    | x::xs as list -> (e::list)::(inserts e xs |> List.map (fun xs' -> x::xs'))

  List.fold (fun accum x -> List.collect (inserts x) accum) [[]] list

```

# The algorithm
To get all permutations of a list, we can use the insert algorithm.

First, we have `inserts` function which gives us all the possible ways we can insert an element in a list. For example, if you had a list of `[1;2]`, inserting 3 will give you `[3;1;2]`, `[1;3;2]` and `[1;2;3]`.

Next, we build our permutation list by inserting each element from the original list to each item in our permutation list using `inserts` function.

Here how we can compute permutations of `[1;2;3]`

```
                     insert 1 []
                        |
                     insert 2 [1]
                        |
      +-----------------+----------------+
    insert 3 [1;2]              insert 3 [2;1]
           |                         |
 +---------+--------+      +---------+---------+        
 |         |        |      |         |         | 
[3;1;2] [1;3;2] [1;2;3]   [3;2;1] [2;3;1] [2;1;3]
```

Therefore permuting `[1;2;3]` gives us `[3;1;2]`, `[1;3;2]`, `[1;2;3]`, `[3;2;1]`, `[2;3;1]` and `[2;1;3]`.

# Implementation in F&#35;

The main thing to implement is the `inserts` function.

To operate on a list, we normally use recursion and pattern matching.

First we pattern match on the passed list and deconstruct it to a head and tail. Next we operate on the head. After that, we pass the tail recursively to the same function.

```fsharp
let rec inserts e list =
  match list with
  // if list is empty then return empty
  | [] -> []
  // else deconstruct the list into a head and a tail and
  // prepend head to the result of working on the tail
  | head::tail -> head::(inserts e tail)

inserts 9 [1;2;3] // [1;2;3]
```

Let us change the function to prepend `e` to every head

```fsharp
let rec inserts e list =
  match list with
  | [] -> [e]
  | head::tail -> e::head::(inserts e tail)

inserts 9 [1;2;3] // [9;1;9;2;9;3;9]
```

Next, we change the function to prepend `e` to the slice of list we currently have.

```fsharp
let rec inserts e list =
  match list with
  | [] -> [[e]]
  | head::tail -> (e::list)::(inserts e tail)

inserts 9 [1;2;3] // [[9;1;2;3];[9;2;3];[9;3];[9]]
```

Notice how the slices keep losing their heads? We need to give it back so they can be whole again.

```fsharp
let rec inserts e list =
  match list with
  | [] -> [[e]]
  | head::tail -> (e::list)::(inserts e tail |> List.map (fun tail' -> head::tail'))

inserts 9 [1;2;3] // [[9;1;2;3];[1;9;2;3];[1;2;9;3];[1;2;3;9]]
```

Now that we have the `inserts` function, we use it to compute permutations by starting with an empty list and inserting each element in our original list to each element in our permutations list.

In imperative form, our code would be something like this.

```javascript
let permutations = [[]]
for (let i = 0; i < arr.length; i++) {
  let temp = []
  for (let j = 0; j < permutations.length; j++) {
    temp.push(inserts(arr[i], permutations[j]))
  }
  permutations = [...temp]
}
```

But we want to do this in functional style so we will use `List.fold` to achieve the same thing.

```fsharp
let rec inserts e list =
  match list with
  | [] -> [[e]]
  | head::tail -> (e::list)::(inserts e tail |> List.map (fun tail' -> head::tail'))

let permute list =
  // List.collect is equivalent to flatMap in javascript
  List.fold (fun accum x -> List.collect (inserts x) accum) [[]] list
```

Because `inserts` function is only used inside `permute`, we will move it inside `permute`

```fsharp
let permute list =
  let rec inserts e list =
    match list with
    | [] -> [[e]]
    |  head::tail -> (e::list)::(inserts e tail |> List.map (fun tail' -> head::tail'))

  List.fold (fun accum x -> List.collect (inserts x) accum) [[]] list
```

Finally, we make our code more concise by renaming head and tail to x and xs respectively and by using the [function keyword for pattern matching](https://fsharpforfunandprofit.com/posts/match-expression/#the-function-keyword).

```fsharp
let permute list =
  let rec inserts e = function
    | [] -> [[e]]
    | x::xs as list -> (e::list)::(inserts e xs |> List.map (fun xs' -> x::xs'))

  List.fold (fun accum x -> List.collect (inserts x) accum) [[]] list

```

**Bonus**: We can get to even more concise syntax by replacing `List.map` with list comprehension syntax.

```fsharp
let permute list =
  let rec inserts e = function
    | [] -> [[e]]
    | x::xs as list -> (e::list)::[for xs' in inserts e xs -> x::xs']

  List.fold (fun accum x -> List.collect (inserts x) accum) [[]] list
```

## References
* https://stackoverflow.com/questions/1526046/f-permutations
* https://www.topcoder.com/generating-permutations/