9

作为枚举集合的更大问题的一部分，我需要编写一个 OCaml 函数“选择”，它接受一个列表并输出作为由该列表的元素组成的所有可能大小为 k 的序列的列表（不重复序列通过置换从彼此获得）。它们放在最终列表中的顺序无关紧要。

例如，

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

有任何想法吗？

我想让整个事情变得懒惰，输出一个懒惰的列表，但如果你有一个严格的解决方案，那也会非常有用。

4

3 回答 3

9

这是一个严格且次优的版本。我希望很清楚。它通过假设输入列表中没有重复项并仅生成与原始列表中的顺序相同的子列表来避免重复项。

长度计算可以通过将l的长度作为 的参数来考虑choose。这将使代码的可读性降低，但效率更高。

对于懒惰的版本，在代码上撒上“懒惰”和“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))
;;
于 2010-10-19T15:21:13.443 回答
8

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

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

前两种情况来自二项式系数的属性，更具体地说：n choose 0 = 1对于所有n包括n=0（这就是为什么首先处理这种情况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组合都在那里！

于 2010-10-19T18:01:23.443 回答
3

为了完整起见，我将最终代码放在这里，它将来自 Pascal 的严格代码与我的懒惰的东西和所有其他 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

评估“选择 k ls n”的结果是一个惰性列表，其中包含列表 ls 的 k 个元素的所有选择，其中 ls 的大小最大为 n。请注意，正如 Pascal 所指出的，由于枚举发生的方式，函数选择不会涵盖无限列表的所有选择。

谢谢，这真的很有用！

最好的，Surikator。

于 2010-10-19T17:33:51.683 回答