Permutations F #

Question

I need to generate permutations in this 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 problems with this code. For example, list items must be unique. In addition, this is more or less the same approach that I would use when creating a direct implementation in any other language. Is there a better way to implement this in F #.

Thank!

Answer 1

To rearrange 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 "distrib" function distributes the given element among all positions in the list, for example:

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

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

The distribution function will be slow for large lists, since 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 best part about this code is that it returns a sequence of permutations, rather than generating them all at once.

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

Answer 2

Here is the solution I gave in my F # book for scientists (pp. 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 3

It depends on what you mean by "better." I would think this is a little more elegant, but it might 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 items, although this will result in duplicate permutations.

Answer 4

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

 let rec inserts xl = 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 xp } 

Answer 5

In the spirit of Kearle's suggestion, here is a version of understanding the sequence

 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 item from a list

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

Answer 6

IMHO the best solution should be facilitated by the fact that F # is a functional language, so the solution should be as close as possible to the definition of what we mean by substituting there as much as possible. Thus, a permutation is such an instance of a 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 in a beautiful way:

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

taken from erlang programming book

The list recognition operator is used, in the solution mentioned here by other stackoverflowers, there is an auxiliary function that does similar work basically, I voted for the solution without any visible loops, etc., only a pure function definition