F# permutations

For permutations of small lists, I use the following code:

let distrib e L =
    let rec aux pre post = 
        seq {
            match post with
            | [] -> yield (L @ [e])
            | h::t -> yield (List.rev pre @ [e] @ post)
                      yield! aux (h::pre) t 
        }
    aux [] L

let rec perms = function 
    | [] -> Seq.singleton []
    | h::t -> Seq.collect (distrib h) (perms t)

It works as follows: the function "distrib" distributes a given element over all positions in a list, example:

distrib 10 [1;2;3] --> [[10;1;2;3];[1;10;2;3];[1;2;10;3];[1;2;3;10]]

The function perms works (recursively) as follows: distribute the head of the list over all permutations of its tail.

The distrib function will get slow for large lists, because it uses the @ operator a lot, but for lists of reasonable length (<=10), the code above works fine.

One warning: if your list contains duplicates, the result will contain identical permutations. For example:

perms [1;1;3] = [[1;1;3]; [1;1;3]; [1;3;1]; [1;3;1]; [3;1;1]; [3;1;1]]

The nice thing about this code is that it returns a sequence of permutations, instead of generating them all at once.

Of course, generating permutations with an imperative array-based algorithm will be (much) faster, but this algorithm has served me well in most cases.

Here's the solution I gave in my book F# for Scientists (page 166-167):

let rec distribute e = function
  | [] -> [[e]]
  | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]

let rec permute = function
  | [] -> [[]]
  | e::xs -> List.collect (distribute e) (permute xs)