This is Algorithm A from Functional Programs for Generating Permutations (Topor, 1982). The author states that the algorithm was described in TAoCP Vol 1.
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#.