i've written following combinations , permutations functions f# project, i'm quite aware they're far optimised.
/// rotates list 1 place forward. let rotate lst = list.tail lst @ [list.head lst] /// gets rotations of list. let getrotations lst = let rec getall lst = if = 0 [] else lst :: (getall (rotate lst) (i - 1)) getall lst (list.length lst) /// gets permutations (without repetition) of specified length list. let rec getperms n lst = match n, lst | 0, _ -> seq [[]] | _, [] -> seq [] | k, _ -> lst |> getrotations |> seq.collect (fun r -> seq.map ((@) [list.head r]) (getperms (k - 1) (list.tail r))) /// gets permutations (with repetition) of specified length list. let rec getpermswithrep n lst = match n, lst | 0, _ -> seq [[]] | _, [] -> seq [] | k, _ -> lst |> seq.collect (fun x -> seq.map ((@) [x]) (getpermswithrep (k - 1) lst)) // equivalent: | k, _ -> lst |> getrotations |> seq.collect (fun r -> list.map ((@) [list.head r]) (getpermswithrep (k - 1) r)) /// gets combinations (without repetition) of specified length list. let rec getcombs n lst = match n, lst | 0, _ -> seq [[]] | _, [] -> seq [] | k, (x :: xs) -> seq.append (seq.map ((@) [x]) (getcombs (k - 1) xs)) (getcombs k xs) /// gets combinations (with repetition) of specified length list. let rec getcombswithrep n lst = match n, lst | 0, _ -> seq [[]] | _, [] -> seq [] | k, (x :: xs) -> seq.append (seq.map ((@) [x]) (getcombswithrep (k - 1) lst)) (getcombswithrep k xs)
does have suggestions how these functions (algorithms) can sped up? i'm particularly interested in how permutation (with , without repetition) ones can improved. business involving rotations of lists doesn't efficient me in retrospect.
update
here's new implementation getperms function, inspired tomas's answer.
unfortunately, it's not fast existing one. suggestions?
let getperms n lst = let rec getpermsimpl acc n lst = seq { match n, lst | k, x :: xs -> if k > 0 r in getrotations lst yield! getpermsimpl (list.head r :: acc) (k - 1) (list.tail r) if k >= 0 yield! getpermsimpl acc k [] | 0, [] -> yield acc | _, [] -> () } getpermsimpl list.empty n lst
i noticed updated getperms function contains duplicates. here's crack @ dupe-free version. comments speak themselves. hardest part writing efficient distrib function, because concatenation operator has used somewhere. luckily it's used on small sublists, performance remains reasonable. getallperms code below generates permutations of [1..9] in around quarter of second, 10-element permutations in around 2.5 seconds.
edit: funny, didn't @ tomas' code, combinations function , picks function identical.
// ordered picks {x_i1, x_i2, .. , x_ik} of k out of n elements {x_1,..,x_n} // i1 < i2 < .. < ik let picks n l = let rec aux nleft acc l = seq { match nleft,l | 0,_ -> yield acc | _,[] -> () | nleft,h::t -> yield! aux (nleft-1) (h::acc) t yield! aux nleft acc t } aux n [] l // distribute element y on list: // {x1,..,xn} --> {y,x1,..,xn}, {x1,y,x2,..,xn}, .. , {x1,..,xn,y} let distrib y l = let rec aux pre post = seq { match post | [] -> yield (l @ [y]) | h::t -> yield (pre @ y::post) yield! aux (pre @ [h]) t } aux [] l // permutations of single list = head of list distributed // on permutations of tail let rec getallperms = function | [] -> seq.singleton [] | h::t -> getallperms t |> seq.collect (distrib h) // k-element permutations out of n elements = // permutations of ordered picks of length k combined let getperms2 n lst = picks n lst |> seq.collect getallperms
edit: more code in response comments
// generates cartesian outer product of list of sequences ll let rec outerproduct = function | [] -> seq.singleton [] | l::ls -> l |> seq.collect (fun x -> outerproduct ls |> seq.map (fun l -> x::l)) // generates n-element combination list l let getpermswithrep2 n l = list.replicate n l |> outerproduct
Comments
Post a Comment