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.

enter image description here

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)

• Shaun Luttin: You demonstrated three alternative techniques. Pattern matching, removing the type annotations, and using [] instead of List.empty<'t>. I had figured that the compiler would complain about the use of [] for an empty list. Thank you for the answer.
• Chester Husk: take a look at the implementation of List.empty here, you can see that the compiler itself uses [] in this way. [] and List.empty are just two names for the same value. You also don't necessarily need to provide a type argument 't for List.empty most of the time. The compiler can infer what the 't should be based on usage.

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.

• Shaun Luttin: Thank you for demonstrating the removal of type annotations and demonstrating the q |> List.length approach. I was surprised to see that we could use [] to represent an empty list. I thought that the compiler would throw a type error due to the vagueness of the empty list's type.
• Shaun Luttin: It was also good to learn about encapsulating the recursive function.