在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)从每个元素生成排列.指数.请参阅Rosetta Code示例.我怀疑它们具有相似的空间复杂性.

Answer 2

这是一个生成排列流（即惰性列表）的解决方案。这避免了必须立即将整个列表保存在内存中。如果您只需要有限数量的排列，它可以让您处理更长的列表。

为了让事情变得简单，我使用 Jane Street Core 作为我的基础库。

open Core.Std

let permutations lst =
    let lstar = Array.of_list lst in
    let len = Array.length lstar in
    let ks = List.range 1 (len + 1) in
    let indices = Int.Set.of_list (List.range 0 len) in
    let choose k (v, indices, res) =
        let ix = Option.value_exn (Int.Set.find_index indices (v mod k)) in
        (v / k, Int.Set.remove indices ix, lstar.(ix) :: res)
    in
    let perm i =
        let (v, _, res) =
            List.fold_right ks ~f: choose ~init: (i, indices, [])
        in
        if v > 0 then None else Some res
    in
    Stream.from perm

这是此实现的一个会话：

# let s = permutations ['a'; 'b'; 'c'; 'd'];;
val s : char list Stream.t = <abstr>
# Stream.npeek 100 s;;
- : char list list =
[[d; c; b; a]; [d; c; a; b]; [d; b; a; c]; [c; b; a; d]; [d; b; c; a];
 [d; a; c; b]; [d; a; b; c]; [c; a; b; d]; [c; b; d; a]; [c; a; d; b];
 [b; a; d; c]; [b; a; c; d]; [c; d; b; a]; [c; d; a; b]; [b; d; a; c];
 [b; c; a; d]; [b; d; c; a]; [a; d; c; b]; [a; d; b; c]; [a; c; b; d];
 [b; c; d; a]; [a; c; d; b]; [a; b; d; c]; [a; b; c; d]]
# let s = permutations (List.range 0 10);;
val s : int list Stream.t = <abstr>
# Stream.iter ignore s;;
- : unit = ()
# Stream.count s;;
- : int = 3628800
# fact 10;;
- : int = 3628800

关键思想是，您可以通过某种方式对排列进行编号，从而可以轻松地从索引中提取排列本身。直觉类似于对整数的十进制表示进行编号的方式。要从索引中提取 4 位数字的十进制表示形式，您可以执行以下操作：

let digits i =
    let ks = [10;10;10;10] in
    let extract k (v, result) = (v / k, v mod k :: result) in
    let (_, res) = List.fold_right ks ~f: extract ~init: (i, []) in
    res

请注意，每次都使用 10 作为除数。要提取排列，您可以执行非常相似的操作，只不过您使用 n, n - 1, n - 2, ..., 1 作为除数。