algorithm - 在 OCaml 中编写置换函数的理想方式

Question

给定一个列表，并输出其所有排列的列表。

这是我的想法:

递归地，hd::tl 的排列是将hd 分布到tl 排列的每个列表中。通过分发 hd，我的意思是将 hd 插入列表中的每个可能的位置。

例如，将 1 分配到 [2;3] 会生成 [[1;2;3];[2;1;3];[ 2;3;1]]。

代码如下

let distribute c l =
  let rec insert acc1 acc2 = function
    | [] -> acc2
    | hd::tl ->
      insert (hd::acc1) ((List.rev_append acc1 (hd::c::tl)) :: acc2) tl
  in 
  insert [] [c::l] l

let rec permutation = function
  | [] -> [[]]
  | hd::tl -> 
    List.fold_left (fun acc x -> List.rev_append (distribute hd x) acc) [] (permutation tl)

---

我猜上面的代码是正确的。

我的问题是:有没有更好的方法(在简单性、性能、空间效率等方面)在 OCaml 中编写排列？

Answer 1

其他方法包括 a) 对于每个元素，将其添加到列表中不包括该元素的每个排列中，或者 b) 从 n!指数。查看Rosetta Code例子。我怀疑它们具有相似的空间复杂度。