Вычисление набора всех подмножеств (набор мощности)

Question

Я пытаюсь получить функцию (заданную как параметр набор), чтобы вернуть набор, элементами которого являются все подмножества, образованные из основного набора. Пример: {1; 2; 3} -> {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }

Но я не знаю, как создать модуль, который позволяет мне работать с набором множеств. Какой тип я должен определить?

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

Если вы хотите использовать стандартный 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"]]