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#.