functional-programming - 用函数式语言生成所有排列

Question

作为一项学术练习，我尝试使用 OCaml 语言生成列表的所有可能排列，但不能使用 for 循环。我可以使用变量、递归、模式匹配和 if-else 控件。

到目前为止，这是我的想法:因为我可以使用递归，如果我想生成列表 [1;2;3] 的所有 6 个排列，那么我可以使用 h::t 进行模式匹配，其中 h 是1 和 t 是 [2;3]，假设我有 [2;3] 的所有排列。然后我想遍历 [2;3] 的所有这些排列，在每个可能的坐标中插入 1:0、1 和 2。因此，例如 [2;3] 我想生成 [1;2;3]和 [2;1;3] 和 [2;3;1]，然后对于 [3;2] 我想生成 [1;3;2] 和 [3;1;2] 和 [3;2; 1].

但是也存在一些明显的问题。一是我需要用这些工具告诉计算机如何插入——但我已经想通了。我还需要“循环”遍历所有较小的排列，然后循环遍历它们的所有坐标，这是我不允许做的事情。那就是我被困的地方。

这是我所做的:

(* This successfully does insertion of v into l at pos.*)
let rec insert_at_i (v: int) (l: int list) (pos: int) : int list =
  begin match (l, pos) with
    | (_, 0) -> v::l 
    | ([], _) -> failwith "invalid insert_at_i"
    | (h::t, _) -> h::(insert_at_i v t (pos - 1))
  end

(* This finds the length of a list.*)
let rec len (l: int list) : int =
  begin match l with
    | [] -> 0
    | h::t -> (1 + (len t))
  end

(* Here I'm trying to take a value like 1 and a list like [2;3] and 
generate the list of all lists where 1 is inserted somewhere.  Since I 
can't loop, I tried thinking of a way to pattern-match, but it's not 
working out.  I tried to make extra parameters for basically keeping 
track of the recursion's results as I go, but I'm running into the 
problem that in a functional language like this, variables can't be re-
written with their side-effects stored, so to speak. *)
let rec insert_ith_at_i (v: int) (l: int list) (pos: int) (sofar: int list list): int list list =
  if (l = []) then [[v]]
  else if (pos > (len l)) then sofar
  else (insert_ith_at_i v l (pos + 1) )

感谢任何指导或命中。

Answer 1

这是一个解决方案 - 我首先定义了一些辅助函数:

let ( ^^ ) e ll = List.map (fun x -> e::x) ll

此函数向列表中包含的每个列表添加一个元素:

1 ^^ [[2; 3]; [3; 2]]  gives : [[1; 2; 3]; [1; 3; 2]]

然后是 permut 函数:

let rec permut l r =  /* l : left, r right */
    match r with 
    | [] -> [[]]
    | [x] -> x ^^ (permut [] l)
    | x::t -> let s = permut (x::l) t in 
              (x ^^ (permut [] (l@t))) @ s;;

 permut [] [1;2;3];

算法运行如下:

• 选择第一个元素'x'，
• 计算剩余元素的所有排列
• 将 x 添加到每个计算的排列
• 将此元素放在“左”列表中
• 选择第二个元素
• 计算其他元素的排列:第一个保留在左侧列表中，“t”列表的剩余元素...等等。