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

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

这是我的想法:

递归地，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中的排列？

最佳答案

这是一种生成排列流(即惰性列表)的解决方案。这样避免了必须一次将整个列表保存在内存中。如果只需要有限数量的排列，则可以使用更长的列表。

为简化起见，我使用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

这是有关此实现的 session :

# 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作为除数之外，您可以做一些非常相似的事情。

关于algorithm - 在OCaml中编写置换函数的理想方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20196133/