懒惰“n选择k”在OCaml

问题描述

作为列举一个集合的更大问题的一部分，我需要编写一个OCaml函数'choose'，它将列表和输出作为由该列表的元素构成的所有可能的大小为k的序列的列表（不重复可通过置换相互获得的序列）。它们放在最后清单中的顺序是不相关的。

例如，

 选择2 [1; 2; 3; 4] = [[1; 2]; [1; 3]; [1; 4]; [2; 3]; [2; 4]; [3 ; 4]] 
  

有什么想法？

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

解决方案

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

长度计算可以通过传递 l 的长度作为的参数来选择。这会让代码更少可读，但效率更高。

对于懒惰版本，在代码上撒上lazy和Lazy.force...

 让rec选择kl = 
如果k = 0 
则[[]] 
 else 
 let len = List.length l in 
 if len< k 
 then [] 
 else if k = len 
 then [l] 
 else 
 match l with 
 h :: t  - > 
 let start_with_h = 
（List.map（fun sublist  - > h :: sublist）（choose（pred k）t））
 in 
 let not_starting_with_h =选择kt in 
 starting_with_h @ not_starting_with_h 
 | []  - >断言假
 ;; 
 val选择：int  - > '列表 - > '列表列表=< fun> 
 
＃选择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 = 
 |空
 | 'a *'a zlist_t 
和'a zlist_t ='a node_t lazy_t 
 
 let rec lazy_list_append l1 l2 = 
 lazy 
（匹配Lazy.force l1 
 Empty  - > Lazy.force l2 
 | Node（h，lt） - > 
 Node（h，lazy_list_append lt12））
 ;; 
  

As part of a bigger problem of enumerating a set, I need to write an OCaml function 'choose' which takes a list and outputs as the list of all possible sequences of size k made up of elements of that list (without repeating sequences which can be obtained from each other by permutation). The order they are put in the end list is not relevant.

For example,

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

Any ideas?

I would like to have the whole thing to be lazy, outputting a lazy list, but if you have a strict solution, that'll be very useful too.

解决方案

Here is a strict and suboptimal version. I hope it is clear. It avoids duplicates by assuming there are no duplicates in the input list, and by generating only sublists that are in the same order as in the original list.

The length computation could be factored by passing l's length as an argument of choose. That would make the code less readable but more efficient.

For the lazy version, sprinkle "lazy" and "Lazy.force" on the code...

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

EDIT:

A lazy_list_append as appears necessary from the comments below:

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

这篇关于懒惰“n选择k”在OCaml的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！