OCaml中的"n choose k"懒惰算法

Question

作为枚举集合的一个大问题的一部分，我需要编写一个OCaml函数“choose”，它接受列表并输出由该列表中元素组成的大小为k的所有可能序列的列表（不重复出现可以通过排列相互获得）。它们在最终列表中的顺序并不重要。

例如，

choose 2 [1;2;3;4] = [[1;2];[1;3];[1;4];[2;3];[2;4];[3;4]]

有什么想法吗？

我希望整个过程都是“懒”的，输出一个“懒”列表，但如果你有一个严格的解决方案，那也会非常有用。

- Surikator

---

如果它是惰性的，它的类型不能返回一个列表。一个惰性列表应该足够满足你的需求：http://enfranchisedmind.com/blog/posts/ocaml-lazy-lists-an-introduction/ - Pascal Cuoq

嗨，Pascal。我使用严格的符号表示法编写了示例，以便更容易阅读。是的，我希望它是懒惰的。但我的问题不是如何使用懒惰列表。而是关于特定的“选择”函数。我不知道如何使其从初始列表中选择所有长度为k的可能性。 - Surikator

你的问题很清楚，我只是在评论中提到OCaml中的惰性计算，以防你有所困惑。我相信会有人在答案中提供更有建设性的内容。 - Pascal Cuoq

Answer 1

这里是一份严格但不够优化的代码版本，希望它很清晰。它通过假设输入列表中没有重复项，并仅生成与原始列表中顺序相同的子列表来避免重复。

长度计算可以通过将 l 的长度作为 choose 的参数传递来进行因式分解。这会使代码更高效，但可读性较差。

对于懒惰版本，可以在代码中添加 "lazy" 和 "Lazy.force"。

let rec choose k l =
  if k = 0 
  then [ [] ]
  else
    let len = List.length l in
    if len < k
    then []
    else if k = len
    then [ l ]
    else
      match l with
      h :: t ->
          let starting_with_h =
            (List.map (fun sublist -> h :: sublist) (choose (pred k) t))
          in
          let not_starting_with_h = choose k t in
          starting_with_h @ not_starting_with_h
      | [] -> assert false
;;
  val choose : int -> 'a list -> 'a list list = <fun>

# choose 3 [1; 2; 3; 4; 5; 6; 7] ;;                        
- : int list list =
[[1; 2; 3]; [1; 2; 4]; [1; 2; 5]; [1; 2; 6]; [1; 2; 7]; [1; 3; 4]; [1; 3; 5];
 [1; 3; 6]; [1; 3; 7]; [1; 4; 5]; [1; 4; 6]; [1; 4; 7]; [1; 5; 6]; [1; 5; 7];
 [1; 6; 7]; [2; 3; 4]; [2; 3; 5]; [2; 3; 6]; [2; 3; 7]; [2; 4; 5]; [2; 4; 6];
 [2; 4; 7]; [2; 5; 6]; [2; 5; 7]; [2; 6; 7]; [3; 4; 5]; [3; 4; 6]; [3; 4; 7];
 [3; 5; 6]; [3; 5; 7]; [3; 6; 7]; [4; 5; 6]; [4; 5; 7]; [4; 6; 7]; [5; 6; 7]]

编辑：

根据下面的评论，需要一个lazy_list_append：

type 'a node_t =             
      | Empty
      | Node of 'a * 'a zlist_t
and 'a zlist_t = 'a node_t lazy_t

let rec lazy_list_append l1 l2 =
  lazy 
    (match Lazy.force l1 with
      Empty -> Lazy.force l2 
    | Node (h, lt) ->
    Node (h, lazy_list_append lt l2))
;;

- Pascal Cuoq

---

@Surikator 如果你做得对，@的删除就会随着懒惰而自然发生。也就是说，你的懒惰版本将使用lazy_list_append，这种方法不会像@那样低效。 - Pascal Cuoq

如果您不关心返回值的顺序，则可以使用List.rev_append替换它；这是尾递归，比@更高效。 - nlucaroni

@Surikator 对于懒惰版本，可以将列表的长度作为“choose”的参数传递。如果您希望懒惰地开始枚举无限可能性，则可以使用“type extended_int = Finite of int | Infinite”，但我的算法不是“公平”的：如果输入实际上是无限的，则您永远不会看到某些子列表。您需要将其更改为生成已经看到的元素的所有可能组合。 - Pascal Cuoq

@Surikator，看起来你的版本更好。我不是专家。你的版本在被强制之前会强制l1的第一个元素，但这可能是可取的...我不确定。 - Pascal Cuoq

@Surikator List.length只是问题的冰山一角。无论如何，列表都需要完全评估前len个子列表。如果您想要完全懒惰，您需要改变发射的顺序。请参阅我的公平评论。 - Pascal Cuoq

Answer 2

再次使用Haskell解决方案（因为它更容易使用惰性列表，因为它们是内置的）：

combinations 0 _ = [[]]
combinations k [] = []
combinations k (x:xs) = map (x:) (combinations (k-1) xs) ++ combinations k xs

第一和第二种情况是由二项式系数的性质导出的，更具体地说：对于所有n，包括n = 0，有n choose 0 = 1（这就是为什么要先处理0 choose 0的原因）。另一个是0 choose k = 0。第三个方程式是组合的递归定义的确切翻译。

不幸的是，当你将它应用到无限列表上时，它会返回一个平凡的解：

> take 10 $ combinations 3 [1..]
[[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,2,7],[1,2,8],[1,2,9],[1,2,10],[1,2,11],[1,2,12]]

---

编辑：好的，所以我们真正想要在有限步骤内遍历每个组合。使用上述版本时，我们显然仅使用左侧的表达式 ++ 生成以1开头的组合。我们可以通过定义一个有趣的列表压缩函数来解决这个问题，该函数通过交替选择其参数列表的每个头部（在第二个参数中重要的是非严格）来构建列表：

merge [] ys = ys
merge (x:xs) ys = x:merge ys xs

使用它代替++：

combinations k (x:xs) = map (x:) (combinations (k-1) xs) `merge` combinations k xs

让我们看看：

> let comb_10_3 = combinations 3 [1..10]
> let comb_inf_3 = combinations 3 [1..]
> take 10 comb_inf_3 
[[1,2,3],[2,3,4],[1,3,4],[3,4,5],[1,2,4],[2,4,5],[1,4,5],[4,5,6],[1,2,5],[2,3,5]]
> comb_10_3 `intersect` comb_inf_3 == comb_10_3 
True
> last $ combinations 3 [1..10]
[6,8,10]
> elemIndex [6,8,10] $ combinations 3 [1..]
Just 351

所有的10 choose 3组合都在这里！

- Daniel

---

我更希望看到一个实际工作的Haskell懒惰解决方案，而不是已经构建并指出存在缺陷的失效解决方案。有什么想法吗？ - Pascal Cuoq

实际上，我之前在OCaml中提出的懒惰答案，基于Pascal的严格规定，虽然不能用于无限列表，但适用于任意大小的懒惰列表（只是不包括“无限大小”）=) - Surikator

@Daniel Velkov，PS：不用说了（也就是说，你不必再说了。我们都知道Haskell有多优雅。现在可以停止说了。）。尽管有PS，我还是点赞+1。 - Pascal Cuoq

@Daniel 谢谢你的建议！'合并' 的想法非常优雅，对于处理无限列表绝对是必要的。@Pascal 是的，我们不要讨论 Haskell/Ocaml 的问题了。我们都对自己的选择感到满意，所以让我们保持和平。=) - Surikator

@Daniel，我认为这个问题应该保留“Lazy”标签。我的简短答案将所有“懒惰”的工具都综合运用了。当我谷歌搜索答案时，我使用的关键词是“lazy”。如果能找到这个页面，我会很开心。不管怎样，决定权在你手中。 - Surikator

适当的对角化胜利！顺便说一下，你的merge来自The Reasoned Schemer的mplus_i。另请参阅luqui的这个答案。 - Will Ness

Answer 3

为了完整起见，我在这里放置了最终代码，将Pascal的严格代码与我的懒惰代码和所有其他有用的注释结合起来。

定义了懒惰列表类型，然后是两个辅助懒惰函数（append和map），最后是我们要定义的函数“选择”。

type 'a node_t =
  | Nil                                            
  | Cons of 'a * 'a t
and 'a t = ('a node_t) Lazy.t

let rec append l1 l2 = 
match Lazy.force l1 with
    | Nil -> l2 
    | Cons (a, l) -> lazy (Cons (a, append l l2))

let rec map f ll = lazy (
match Lazy.force ll with
    | Nil ->    Nil
    | Cons(h,t) -> Cons(f h, map f t) )

let rec choose k l len =
  if k = 0 
  then lazy (Cons(lazy Nil,lazy Nil))
  else
        if len < k
        then lazy Nil
        else if k = len
    then lazy (Cons (l,lazy Nil))
    else
      match Lazy.force l with
          | Cons(h,t) ->  let g h sublist = lazy (Cons (h,sublist))
                          in let starting_with_h = (map (g h) (choose (k-1) t (len-1)))
                          in let not_starting_with_h = choose k t (len-1)
                          in append starting_with_h not_starting_with_h
          | Nil -> assert false

"choose k ls n"的计算结果是一个惰性列表，其中包含ls列表中k个元素的所有选择，ls的大小不超过n。需要注意的是，正如Pascal指出的那样，由于枚举方式的限制，函数choose无法覆盖无限列表的所有选择。

谢谢，这真的很有用！

最好的祝愿， Surikator。

- Surikator