在函数式编程语言中生成所有排列

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) )

任何指导或提示都会受到赞赏。

- Addem

---

就算不值得一提，任何循环都可以表示为递归。因此，您可以循环遍历任何想要循环遍历的内容。 - Jeffrey Scofield

https://rosettacode.org/wiki/Permutations 下次请先尝试谷歌搜索。 - Jared Smith

@JaredSmith 网站无法加载，似乎暂时出现了问题。此外，我通过谷歌搜索，找到许多包含for循环的结果。 - Addem

@Addem 我刚刚成功地加载了它（在Chrome 60 Linux上）。这是OCaml实现的链接 https://rosettacode.org/wiki/Permutations#OCaml - Jared Smith

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添加到每个计算出的排列中
• 将该元素放入“left”列表中
• 选择第二个元素
• 计算其他元素的排列：
• 前几个元素在“left”列表中保持不变
• 剩下的元素在“t”列表中
• 以此类推。

- Pierre G.