Home > Uncategorized > List permutations in F#

List permutations in F#

let (++) a b = List.append a b

let cons x xs = x::xs

 

let rec permute (xss : ‘a list) : ‘a list list =

    let permuteFirst (ls : ‘a list) : ‘a list list =

        let rec f yss xss =

            match xss with

            | [] -> []

            | x::xs -> (x::yss++xs) :: (f (yss ++ [x]) xs)

        f [] ls

    let permuteRest (lss : ‘a list) : ‘a list list =

            match lss with

            | [] -> raise (new System.Exception());

            | (l::ls) -> List.map (cons l) (permute ls)

    match xss with

    | [] -> []

    | [x] -> [[x]]

    | x::xs -> permuteFirst xss |> List.map permuteRest |> List.concat       

 

permute [1;2;3] gives [[1; 2; 3]; [1; 3; 2]; [2; 1; 3]; [2; 3; 1]; [3; 1; 2]; [3; 2; 1]].

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: