I have (we have) implemented the functional permutation generator from (Topor, 1982).
The full source of the implementation is here.
As usual I would like feedback on how to make the code more readable, more aligned with canonical F# styles and conventions, and/or different from how it is right now. For instance:
- are there more conventional ways to use
- where would
if...else...be more appropriate than pattern matching is?
- would list comprehension be more canonical than recursion?
Here is the code we implemented.
nextPerm is what we would expect client applications to call. It generates the next permutation in reverse lexographic order, so that ABC will generate BAC.
let next3 ps qs rs = let rec genRev (ps: 't list) qs rs ss = match ps with | _ when ps = rs -> ss | _ when ps = qs -> genRev ps.Tail qs rs (rs.Head::ss) | _ -> genRev ps.Tail qs rs (ps.Head::ss) genRev ps qs rs (qs.Head::rs.Tail) let rec firstLess (ps: 't list) a = match ps with | _ when ps.Head < a -> ps | _ -> firstLess ps.Tail a let next2 ps rs = match rs with |  -> None | _ -> let qs = firstLess ps rs.Head let permutation = next3 ps qs rs Some (permutation) let rec firstUp ps = match ps with | [ _ ] ->  | psHead::psTail when psHead < psTail.Head -> psTail | _ -> firstUp ps.Tail let nextPerm ps = match ps with |  -> None | _ -> let rs = firstUp ps next2 ps rs
We can use
permute to generate the list of all permutations. (The suggested implementation from the article is unfortunately not tail optimized.)
let rec permute ps = match ps with | None ->  | Some prev -> let ns = nextPerm prev prev::(permute ns)
All of the functions except for
genRev are public to facilitate the unit testing.