Computing permutations of a list in F#

TL;DR, here is the final code.

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#

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.

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

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.

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.

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.

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.

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

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.

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.

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/

Comments

[Adam Davidson]

This is brilliant. Thanks for sharing it. Can I ask why you used the keyword function in the parameter to List.map? There is no pattern matching going on here and it seems that fun would have done the same job, or am I missing something?

List.map (function xs' -> x::xs')

vs

List.map (fun xs' -> x::xs')

[Mohamed Dahir]

I didn't notice that until now, thanks for catching the error. It is now fixed.

[Adam Davidson]

Thanks Mohamed. I didn't see it as an error, I wondered if I was going to learn something new about F#. I'm still getting to grips with it myself.