Combinations and Permutations in F#
- by Noldorin
I've recently written the following combinations and permutations functions for an F# project, but I'm quite aware they're far from optimised.
/// Rotates a list by one place forward.
let rotate lst =
List.tail lst @ [List.head lst]
/// Gets all rotations of a list.
let getRotations lst =
let rec getAll lst i = if i = 0 then [] else lst :: (getAll (rotate lst) (i - 1))
getAll lst (List.length lst)
/// Gets all permutations (without repetition) of specified length from a list.
let rec getPerms n lst =
match n, lst with
| 0, _ -> seq [[]]
| _, [] -> seq []
| k, _ -> lst |> getRotations |> Seq.collect (fun r -> Seq.map ((@) [List.head r]) (getPerms (k - 1) (List.tail r)))
/// Gets all permutations (with repetition) of specified length from a list.
let rec getPermsWithRep n lst =
match n, lst with
| 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 all combinations (without repetition) of specified length from a list.
let rec getCombs n lst =
match n, lst with
| 0, _ -> seq [[]]
| _, [] -> seq []
| k, (x :: xs) -> Seq.append (Seq.map ((@) [x]) (getCombs (k - 1) xs)) (getCombs k xs)
/// Gets all combinations (with repetition) of specified length from a list.
let rec getCombsWithRep n lst =
match n, lst with
| 0, _ -> seq [[]]
| _, [] -> seq []
| k, (x :: xs) -> Seq.append (Seq.map ((@) [x]) (getCombsWithRep (k - 1) lst)) (getCombsWithRep k xs)
Does anyone have any suggestions for how these functions (algorithms) can be sped up? I'm particularly interested in how the permutation (with and without repetition) ones can be improved. The business involving rotations of lists doesn't look too efficient to me in retrospect.
Update
Here's my new implementation for the getPerms function, inspired by Tomas's answer.
Unfortunately, it's not really any fast than the existing one. Suggestions?
let getPerms n lst =
let rec getPermsImpl acc n lst = seq {
match n, lst with
| k, x :: xs ->
if k > 0 then
for r in getRotations lst do
yield! getPermsImpl (List.head r :: acc) (k - 1) (List.tail r)
if k >= 0 then yield! getPermsImpl acc k []
| 0, [] -> yield acc
| _, [] -> ()
}
getPermsImpl List.empty n lst
