Computing a set of all subsets (power set)

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?

回答1:

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

And here is an example of usage:

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

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)

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

Now we can run it:

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

回答2:

If you want to use the standard Set module, you can work with sets of strings (say) and sets of sets of strings like this:

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