This is Algorithm A from Functional Programs for Generating Permutations (Topor, 1982).
We have implemented Algorithm A in F# as follows.
let rec put (a: 't) (p: List<'t>) (q: List<'t>) : List<'t> = if p = q then a :: q else p.Head :: (put a p.Tail q) // a: an element // p: a list of elements // q: a sublist of p // ps: a list of permutations let rec insert (a: 't) (p: List<'t>) (q: List<'t>) (ps: List<List<'t>>) : List<List<'t>> = if q.Length = 0 then (put a p q) :: ps else (put a p q) :: (insert a p q.Tail ps) let rec mapinsert (a: 't) (ps: List<List<'t>>) : List<List<'t>> = if ps.Length = 0 then List.empty<List<'t>> else insert a ps.Head ps.Head (mapinsert a ps.Tail) // x: a list of elements // returns a list of permutations let rec permute1 (x: List<'t>) : List<List<'t>> = if x.Length = 0 then [x] else mapinsert x.Head (permute1 x.Tail)
Here is a usage example
permute1 [1;2;3] |> List.iter (printf "%A ") // [1; 2; 3] [2; 1; 3] [2; 3; 1] [1; 3; 2] [3; 1; 2] [3; 2; 1]
We would like a review to make our F# more canonical. That is, we would like to adjust our code to be in keeping with common F# styles and techniques.
Alternatively, we would like a reviewer to show alternative techniques (if not better ones) for implementing Algorithm A in F#.