Implementation of Permutation Algorithm A from Topor, 1982
Echoing Henrik's answer, I'd agree that the implementation looks fairly idiomatic already.

The only material change I'd make is changing all uses of List.length to explicit pattern matching with an empty list case.  This is because List.length is an O(n) call due to the linked list implementation of F# Lists, when all you really care about is if the list is empty. As an example:

module AlgorithmA =
  let rec put a p q =
    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 p q ps =
    match q with
    | [] -&gt; put a p [] :: ps
    | _::qs as q' -&gt; put a p q' :: insert a p qs ps

  let rec mapInsert a ps =
    match ps with
    | [] -&gt; []
    | x::xs -&gt; insert a x x (mapInsert a xs)

  // x: a list of elements
  // returns a list of permutations
  let rec permute1 x = 
    match x with
    | [] -&gt; [[]] // return an list containing the empty list 
    | x::xs -&gt; mapInsert x (permute1 xs)