例如，
选择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
发布评论