F# permutations

Question

I need to generate permutations on a given list. I managed to do it like this

let rec Permute (final, arr) = 
    if List.length arr > 0 then
        for x in arr do
            let n_final = final @ [x]
            let rest = arr |> List.filter (fun a -> not (x = a))
            Permute (n_final, rest)
    else
        printfn "%A" final

let DoPermute lst  = 
    Permute ([], lst)

DoPermute lst

There are obvious issues with this code. For example, list elements must be unique. Also, this is more-less a same approach that I would use when generating straight forward implementation in any other language. Is there any better way to implement this in F#.

Thanks!

Answer 1

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)

Answer 2

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.

Answer 3

Here's another sequence-based version, hopefully more readable than the voted answer. This version is similar to Jon's version in terms of logic, but uses computation expressions instead of lists. The first function computes all ways to insert an element x in a list l. The second function computes permutations. You should be able to use this on larger lists (e.g. for brute force searches on all permutations of a set of inputs).

let rec inserts x l =
  seq { match l with
        | [] -> yield [x]
        | y::rest ->
            yield x::l
            for i in inserts x rest do
              yield y::i
      }

let rec permutations l =
  seq { match l with
        | [] -> yield []
        | x::rest ->
            for p in permutations rest do
              yield! inserts x p
      }

Answer 4

It depends on what you mean by "better". I'd consider this to be slightly more elegant, but that may be a matter of taste:

(* get the list of possible heads + remaining elements *)
let rec splitList = function
| [x] -> [x,[]]
| x::xs -> (x, xs) :: List.map (fun (y,l) -> y,x::l) (splitList xs)

let rec permutations = function
| [] -> [[]]
| l -> 
    splitList l 
    |> List.collect (fun (x,rest) ->
         (* permute remaining elements, then prepend head *)
         permutations rest |> List.map (fun l -> x::l))

This can handle lists with duplicate elements, though it will result in duplicated permutations.