Implementation of Permutation Algorithm B from Topor, 1982

Question

This is Algorithm B from Functional Programs for Generating Permutations (Topor, 1982).

enter image description here

We have implemented Algorithm B in an F# recursive module as follows.

module rec Permutations.Permute2
let removeFirst (list: List<'t>) (item: 't): List<'t> =
 match list with
 | [] -> []
 | head::tail when head = item -> tail
 | head::tail -> head :: (removeFirst tail item)
let mapcons (a: 't) (ps: List<List<'t>>) (qs: List<List<'t>>): List<List<'t>> =
 match ps with
 | [] -> qs
 | head::tail -> (a :: head) :: mapcons a tail qs
let mapperm (x: List<'t>) (y: List<'t>): List<List<'t>> = 
 match y with 
 | [] -> []
 | head::tail -> 
 let permuteNext = permute (removeFirst x head)
 let mappermNext = mapperm x tail
 mapcons head permuteNext mappermNext
let permute (x: List<'t>) : List<List<'t>> = 
 match x with 
 | [] -> [ [] ]
 | _ -> mapperm x x

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 B in F#.

• 200_success: Have you tested this code? Since removeFirst calls itself, I believe it needs to be defined using let rec. Also, you have a circular dependency between mapperm and permute.
• Shaun Luttin: @200_success removeFirst can call itself because it is inside a recursive module. I've added that line to the answer. maperm and permute are mutually recursive, which is also allowed in a recursive module.
• Fyodor Soikin: Well, in that case, you shouldn't have had rec on the other three functions.
• Shaun Luttin: Good point... removed.

Answer 1

Overall the code is pretty decent, but if you strive for perfection :-), I can offer a few observations from my side.

1. Generics notation

For generic types with a single generic parameter, F# has an alternative syntax, where you put the parameter in front of the constructor, not in angle brackets - e.g. int list instead of List<int> (note the lower-case list by the way - that is also idiomatic).

For example:

let rec mapcons (a: 't) (ps: 't list list) (qs: 't list list): 't list list =

2. Type signatures

Unlike some other ML-style languages (looking at you, Haskell :-), it is not commonplace for F# functions to have explicit type signatures. As a rule, F# code will only have type signatures either in the most tricky places, as documentation, or else in places where the compiler can't do without it, like with objects or interfaces.

Your functions are trivial enough (or at the very least, they don't really gain anything from type signatures) that I would leave the signatures off. For example:

let rec mapcons a ps qs =

3. Explicit recursion

Recursion is bleh. Don't get me wrong, it's super helpful, and the basis of a lot of stuff, we couldn't really live without it. But writing it explicitly is generally bleh. It's hard to get right, and it turns out that most linearly recursive algorithms can be reduced to just a few common patterns (and ultimately - to just fold).

Take your mapcons function: it first prepends a to every list in ps, and then concatenates qs to that. Well, if you want to transform every element of a list, there's an app for that - map:

let mapcons a ps qs = List.map (fun p -> a :: p) ps @ qs

Alternatively, I would consider a list comprehension:

let mapcons a ps qs = [for p in ps -> a :: p] @ qs

This produces the same effect, but looks differently. I'm on the fence about which one I would prefer, but I'm leaning towards the list comprehension.

4. Some trivial mistakes

As already pointed out in the comments (I wasn't quick enough), your removeFirst function needs to be rec, and mapperm + permute should be a recursive block with let rec ... and ....

• Shaun Luttin: Removing the type signatures makes the code a lot easier to read. Thank you.

Answer 2

The only useful "public" function here is permute; all of the others are "private" helper functions. (In particular, mapperm is useless on its own, since it needs to call permute.) Therefore, I would suggest nesting the helper functions within the scope of the permute function.

The naming of the parameters could be improved. In particular, x has the connotation of being a scalar; the parameter to permute would be better named xs. With the scoping suggestion above, and the pluralization convention, you could probably drop the type annotations for the helper functions without much loss in readability.

You use head and tail in a few places for variable names. It would be clearer if you specified pHead, yTail, etc.

To facilitate currying, it is advantageous to arrange function parameters from the "least varying" to the "most varying" one. In particular, a list that is being operated on should appear last. This criticism applies mainly to your removeFirst. If you swapped the parameters, you could take advantage of the function keyword to write the match less verbosely.

I would capitalize mapcons and mapperm to match F# style.

Suggested solution

let rec permute (xs: List<'t>) : List<List<'t>> = 
 let rec removeFirst item = function
 | [] -> []
 | head::tail when head = item -> tail
 | head::tail -> head :: (removeFirst item tail)
 let rec mapCons a ps qs =
 match ps with
 | [] -> qs
 | pHead::pTail -> (a :: pHead) :: mapCons a pTail qs
 let rec mapPerm xs ys =
 match ys with
 | [] -> []
 | yHead::yTail -> mapCons yHead
 (permute (removeFirst yHead xs))
 (mapPerm xs yTail)
 match xs with
 | [] -> [ [] ]
 | _ -> mapPerm xs xs

• Shaun Luttin: You taught me how to make a function "private." That's new to me. Thank you. Question: what are your thoughts on using a recursive module instead of using the rec... and... pattern?
• Shaun Luttin: Another question: during development, we separately tested what are the now "private" functions. E.g. we had a mapCons test, a removeFirst test, et cetera. Is there a way to test those now that we have made those functions "private?"
• 200_success: I don't have any opinion on recursive modules. As for unit testing, see Unit test private methods in F#.

Answer 3

I think there is a little problem with the performance of your implementation. When the number of elements increases (> 8 - 9) the time the algorithm uses to calculate all the permutations growths significantly which causes an "unbearable" delay before the permutation can be used (the function returns). The problem is that the function returns a list of lists, and the solution is to change it to return a sequence of lists as shown below.

module B =
 let remove lst a = lst |> List.splitAt (lst |> List.findIndex ((=) a)) |> fun (l, m) -> l @ (m.Tail))
 let (--) = remove
 let permute data =
 let mapCons a ps qs = Seq.append (ps |> Seq.map (fun p -> a::p)) qs
 let rec doPermute lst =
 match lst with
 | [] -> seq { yield [] }
 | _ -> seq { yield! mapPerm lst lst }
 and mapPerm lstX lstY =
 match lstY with
 | [] -> Seq.empty
 | head::tail -> mapCons head (doPermute (lstX -- head)) (mapPerm lstX tail)
 doPermute data

In this way the first permutation is returned as soon as it has been computed and everything is running more smoothly.

---

Another implementation of the basic B algorithm could be:

module Permutations =
 let remove lst a = lst |> List.splitAt (lst |> List.findIndex ((=) a)) |> (fun (l, m) -> l @ (m.Tail))
 let (--) = remove
 let private doPerm k data = 
 let rec perm m lst result = 
 match m with 
 | _ when m = k -> seq { yield result |> List.rev }
 | _ -> seq { 
 for a in lst do
 yield! perm (m + 1) (lst -- a) (a::result) } 
 perm 0 data [] 
 let permute data = doPerm (data |> List.length) data
 let permuteOf k data = doPerm k data

This version can be used to both permute (p) and permuteOf (p,k) as shown.