计算一组所有子集(功率集) [英] Computing a set of all subsets (power set)
问题描述
我正在尝试获取一个函数(作为集合的参数给定)以返回一个集合,该集合的元素都是从主集合形成的子集. 例如:{1; 2; 3}-> {{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
I am trying to get a function (given as a parameter a set) to return a set whose elements are all the subset formed from the main set. Ex: {1;2;3} -> { {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
但是我不完全知道如何制作一个可以让我使用一组集合的模块.我应该将其定义为哪种类型?
But I don't exactly know how to make a module that lets me work with a set of sets. What type should I define it as?
推荐答案
一组所有子集称为电源设置.要实现算法,您实际上不需要特殊的数据结构,因为您可以用列表表示一个集合.相应地,一组集合将是列表的列表.例如,
A set of all subsets is called a power set. To implement an algorithm you don't really need a special data structure, as you can represent a set with a list. Correspondingly a set of sets would be a list of lists. E.g.,
let rec superset = function | [] -> [[]] | x :: xs -> let ps = superset xs in ps @ List.map (fun ss -> x :: ss) ps
let rec superset = function | [] -> [[]] | x :: xs -> let ps = superset xs in ps @ List.map (fun ss -> x :: ss) ps
这是用法示例:
superset [1;2;3];;
- : int list list = [[]; [1]; [2]; [2; 1]; [3]; [3; 1]; [3; 2]; [3; 2; 1]
如果要使用实数集,如Jeffrey建议的那样.然后,我们将需要对算法进行一些调整,因为Set模块提供了一些不同的接口.
If you want to use real sets, like Jeffrey suggested. Then we will need to adapt the algorithm a little bit, since Set module provides a little bit different interface.
module S = Set.Make(String)
module SS = Set.Make(S) let superset xs = S.fold (fun x ps -> SS.fold (fun ss -> SS.add (S.add x ss)) ps ps) xs (SS.singleton S.empty)
module S = Set.Make(String)
module SS = Set.Make(S) let superset xs = S.fold (fun x ps -> SS.fold (fun ss -> SS.add (S.add x ss)) ps ps) xs (SS.singleton S.empty)
要运行该算法并打印结果,我们需要将其转换回列表,因为OCaml顶层不知道如何打印集:
To run the algorithm and to print the result we need to transform it back to a list, since OCaml toplevel doesn't know how to print sets:
# superset (S.of_list ["1"; "2"; "3"]) |> SS.elements |> List.map S.elements;;
- : S.elt list list =
[[]; ["1"]; ["1"; "2"]; ["1"; "2"; "3"]; ["1"; "3"]; ["2"]; ["2"; "3"];
["3"]]
现在,我们可以泛化算法,以便它可以在任何有序类型上使用.
Now, we can generalize algorithm, so that it will work on any ordered type.
module Superset(T : Set.OrderedType) = struct module S = Set.Make(T)
module SS = Set.Make(S) let of_set xs = S.fold (fun x ps -> SS.fold (fun ss -> SS.add (S.add x ss)) ps ps) xs (SS.singleton S.empty) end
module Superset(T : Set.OrderedType) = struct module S = Set.Make(T)
module SS = Set.Make(S) let of_set xs = S.fold (fun x ps -> SS.fold (fun ss -> SS.add (S.add x ss)) ps ps) xs (SS.singleton S.empty) end
现在我们可以运行它:
# module Superset_of_strings = Superset(String);;
# open Superset_of_string;;
# of_set (S.of_list ["1"; "2"; "3"]) |> SS.elements |> List.map S.elements;;
- : S.elt list list =
[[]; ["1"]; ["1"; "2"]; ["1"; "2"; "3"]; ["1"; "3"]; ["2"]; ["2"; "3"];
["3"]]
这篇关于计算一组所有子集(功率集)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!