Implementation of Permutation Algorithm A from Topor, 1982

Question

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

Answer 1

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
    | [] -> put a p [] :: ps
    | _::qs as q' -> put a p q' :: insert a p qs ps

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

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

Answer 2

There is nothing much to say about the implementation of the algorithm itself. It seems to be a fairly one-to-one implementation of the pseudo code and it looks rather functional to me.

You could though avoid all the argument declaration if you change a few things in the functions as shown below.

Beside that I prefer to encapsulate recursive functions in a wrapper function but that - I think - is a matter of taste:

    let permuteA data = 
        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 = 
            if q |> List.length = 0 then 
                (put a p q) :: ps
            else 
                (put a p q) :: (insert a p q.Tail ps) 

        let rec mapinsert a ps = 
            if ps |> List.length = 0 then 
                [] 
            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 = 
            if x |> List.length = 0 then 
                [x]
            else 
                mapinsert x.Head (permute1 x.Tail)

        permute1 data

---

EDIT

I admit that Husk has a point about List.lengthespecially in mapinsertwhere the length reach as much as (n - 1)! but tests on my computer shows only a pair of seconds in expense for n = 8. The algorithm exhausts the stack for n = 10 anyway...

As an alternative you could use List.isEmpty which seems to have the same performance as Husks version.