すべてのサブセットのセットを計算する（パワーセット）

Question

私は、要素がメインセットから形成されたすべてのサブセットであるセットを返す関数（パラメータとして与えられたセット）を取得しようとしています。 1、2、3} - > {1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{1,2,3} }

しかし、私はセットのセットで動作させるモジュールを作る方法を正確には分かりません。私はそれをどのようなタイプと定義すべきですか？あなたが標準Setモジュールを使用する場合は

Answer 1

セットはpower setと呼ばれています。アルゴリズムを実装するには、実際には特別なデータ構造は必要ありません。リストを使ってセットを表現することができます。これに対応して、集合の集合はリストのリストである。例えば、

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] 

あなたはジェフリーが提案のように、実際のセットを使用したい場合。 Setモジュールは少し異なるインターフェースを提供するので、アルゴリズムを少し変更する必要があります。

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のトップレベルのセットを印刷する方法を知らないため、リストに戻って、それを変換する必要があり、結果を印刷します：

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

ここで、任意の順序付けられたタイプで動作するようにアルゴリズムを一般化することができます。

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

Answer 2

、あなたはこのような文字列（例えば）と、文字列の集合の集合の集合を扱うことができます：すべてのサブセットの

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