(* ------------------------------------------------------------------------------------------- *)
(* Endliche Mengen werden als Listen ohne Wiederholung implementiert.                          *)
(* ------------------------------------------------------------------------------------------- *)

type 'a set = 'a list;;

(* ------------------------------------------------------------------------------------------- *)
(* add x s liefert die Vereinigung von s und {x}, wenn x nicht in s liegt.                     *)
(* ------------------------------------------------------------------------------------------- *)

let add (x: 'a) (s: 'a set): 'a set = x :: s;;

(* ------------------------------------------------------------------------------------------- *)
(* disjoint_union s1 s2 liefert die Vereinigung von s1 und s2, wenn s1 und s2 disjunkt sind.   *)
(* ------------------------------------------------------------------------------------------- *)

let disjoint_union (s1: 'a set) (s2:'a set): 'a set = s1 @ s2;;

(* ------------------------------------------------------------------------------------------- *)
(* big_disjoint_union liefert die Vereinigung einer Liste von disjunkten Mengen.               *)
(* ------------------------------------------------------------------------------------------- *)

let big_disjoint_union (l: 'a set list): 'a set = List.flatten l;;

(* ------------------------------------------------------------------------------------------- *)
(* powerset(s) liefert die Potenzmenge der Menge s.                                            *)
(* ------------------------------------------------------------------------------------------- *)

let rec powerset (s: 'a set): 'a set set = 
  match s with 
      []        -> [[]]
    | (x :: s') -> let p = powerset s' in disjoint_union p (List.map (add x) p);; 

powerset [];;
powerset [1];;
powerset [1;2];;
powerset [1;2;3];;
powerset [1;2;3;4];;

(* ------------------------------------------------------------------------------------------- *)
(* difference s1 s2 liefert die Mengendifferenz s1 \ s2.                                       *)
(* ------------------------------------------------------------------------------------------- *)

let rec difference (s1: 'a set) (s2: 'a set): 'a set = 
  match s1 with 
      []     -> []
    | x :: s -> if List.mem x s2 then difference s s2 else x :: difference s s2;;

difference [1;2;3;4] [];;
difference [1;2;3;4] [2];;
difference [1;2;3;4] [2;4];;
difference [1;2;3;4] [1;2;3];;

(* ------------------------------------------------------------------------------------------- *)
(* partitions s liefert die Menge Part(s) aller Partitionen von s nach der in Aufgabe 2 ange-  *)
(* gebenen "Rekursionsformel".                                                                 *)
(* ------------------------------------------------------------------------------------------- *)

let rec partitions (s: 'a set) = 
  match s with 
      []      -> [[]]
    |  x :: s' -> 
	 let p = powerset s' in 
	   big_disjoint_union (List.map (fun b -> List.map (add (add x b)) (partitions (difference s' b))) p);;

(* ------------------------------------------------------------------------------------------- *)
(* Die restlichen Funktionen sorgen für eine vernünftige Ausgabe der Mengen.                   *)
(* ------------------------------------------------------------------------------------------- *)

let string_of_int_set (s: int set): string = 
  "{" ^ String.concat ", " (List.map string_of_int s) ^ "}";;

let string_of_partition (p: int set set): string = 
  "{" ^ String.concat ", " (List.map string_of_int_set p) ^ "}";;

let print_partitions (s: int set) = 
  let ps = partitions s in 
    print_string ("\nDie Menge " ^ string_of_int_set s ^ " besitzt " ^ string_of_int (List.length ps) ^ " Partitionen:\n\n");
    List.iter (fun p -> print_string (string_of_partition p ^ ",\n")) ps;
    print_string "\n";;

print_partitions [];;
print_partitions [1];;
print_partitions [1;2];;
print_partitions [1;2;3];;
print_partitions [1;2;3;4];;
print_partitions [1;2;3;4;5];;
print_partitions [1;2;3;4;5;6];;
(* print_partitions [1;2;3;4;5;6;7];; *)
(* print_partitions [1;2;3;4;5;6;7;8];; *)
(* print_partitions [1;2;3;4;5;6;7;8;9];; *)
(* print_partitions [1;2;3;4;5;6;7;8;9;10];; *)