functional-programming - 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]]

有任何想法吗？

我希望整个事情都变得懒惰，输出一个懒惰列表，但是如果您有严格的解决方案，那也将非常有用。

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