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

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 2

In the spirit of Cyrl's suggestion, here's a sequence comprehension version

let rec permsOf xs =
  match xs with
  | [] -> List.toSeq([[]])
  | _ -> seq{ for x in xs do
               for xs' in permsOf (remove x xs) do
                 yield (x::xs')}

where remove is a simple function that removes a given element from a list

let rec remove x xs =
  match xs with [] -> [] | (x'::xs')-> if x=x' then xs' else x'::(remove x xs')

Answer 3

IMHO the best solution should alleviate the fact that F# is a functional language so imho the solution should be as close to the definition of what we mean as permutation there as possible. So the permutation is such an instance of list of things where the head of the list is somehow added to the permutation of the rest of the input list. The erlang solution shows that in a pretty way:

permutations([]) -> [[]];
permutations(L) -> [[H|T] H<- L, T <- permutations( L--[H] ) ].

taken fron the "programming erlang" book

There is a list comprehension operator used, in solution mentioned here by the fellow stackoverflowers there is a helper function which does the similar job basically I'd vote for the solution without any visible loops etc, just pure function definition

Answer 4

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 5

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.

Answer 6

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
      }