I have (we have) implemented the functional permutation generator from (Topor, 1982).

enter image description here

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 Option?
  • 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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.