计算所有子集的集合（幂集）

Question

我正在尝试获取一个函数（作为参数给出一个集合）来返回一个集合，该集合的元素都是由主集合形成的子集。 例如：{1;2;3} -> { {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }

但我并不完全知道如何制作一个让我可以使用一组集合的模块。我应该将其定义为什么类型？

Answer 1

所有子集的集合称为幂集。要实现算法，您实际上并不需要特殊的数据结构，因为您可以用列表表示集合。相应地，集合的集合将是列表的列表。例如，

    let rec powerset = function
      | [] -> [[]]
      | x :: xs ->
         let ps = powerset xs in
         ps @ List.map (fun ss -> x :: ss) ps
 

这是一个用法示例：

powerset [1;2;3];;
- : int list list = [[]; [1]; [2]; [2; 1]; [3]; [3; 1]; [3; 2]; [3; 2; 1]

如果你想使用真实的集合，就像杰弗里建议的那样。然后我们需要稍微调整算法，因为 Set 模块提供了一些不同的接口。

    module S = Set.Make(String)

    module SS = Set.Make(S)
    let powerset xs =
      S.fold (fun x ps ->
          SS.fold (fun ss -> SS.add (S.add x ss)) ps ps) xs
             (SS.singleton S.empty)
 

要运行算法并打印结果，我们需要将其转换回列表，因为 OCaml 顶层不知道如何打印集合：

# powerset (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"]]

现在，我们可以推广算法，以便它可以适用于任何有序类型。

    module Powerset(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 Powerset_of_strings = Powerset(String);;
# open Powerset_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"]]

Answer 2

如果您想使用标准

Set

模块，您可以使用字符串集（例如）和字符串集集，如下所示：

# module S = Set.Make(String);;
. . .
# module SS = Set.Make(S);;
. . .

# let s1 = S.singleton "abc";;
val s1 : S.t = <abstr>
# let ss1 = SS.singleton s1;;
val ss1 : SS.t = <abstr>
# List.map S.elements (SS.elements ss1);;
- : S.elt list list = [["abc"]]