[OCaml]#6 今までの改良＆powerset(べき集合)

さっき書いた、 [OCaml]#5 和集合　積集合　差集合　対称差集合のunion、intersectionについて、このプログラムはO(n)であるcontainをn回再帰しているのでO(n^2)の手間がかかる。
ここで、引数として与えるリストがソート済みならば、O(n)でもっと早く実行できる。


引数のリストは昇順にソートされているので、２つのリストの先頭の要素つまり最小値を取り出し、値が違えば小さい方と同じ値はもう１つのリストには含まれていないことがわかる。intersectionも同様にして求めると、

let rec union l1 l2 =
  match (l1,l2) with
    (_,[]) -> l1
  | ([],_) -> l2
  | (h1::t1,h2::t2) -> if(h1=h2) then h1::(union t1 t2)
                  else if(h1<h2) then h1::(union t1 l2)
                  else h2::(union l1 t2)
;;

let rec intersection l1 l2 =
  match (l1,l2) with
    ((_,[]) | ([],_)) -> [] (* 片方のリストが空なら空リストを返す *)
  | (h1::t1,h2::t2) -> if(h1<h2) then intersection t1 l2
                  else if(h1>h2) then intersection l1 t2
                  else h1::(intersection t1 t2)
;;

最後に、あるリストを与えた時にそのリストのべき集合を返すpowersetを考える。
例えば、powerset [1;2;3;]と実行すると、[[]; [1]; [2]; [3]; [1; 2]; [1; 3]; [2; 3]; [1; 2; 3]]を返すという具合である。

これは再帰的に考えると、n個の要素からなる集合のべき集合は、n-1個の要素からなる集合のべき集合を求め、それとそれの各要素にn個目を加えたものの和集合である。 この、べき集合の各要素（要素といってもリストだが）にn個目を加える作業は別メソッドで定義した。powerset2は、リストのリストと、追加する要素を受け取り、リストのリストから先頭のリストを取り出し、要素を加えたものと加えないものを計算し、残りは再帰的に求める。

let rec powerset2 element listInList =
  match listInList with
    [] -> []
  | h::t -> h :: (element::h) :: (powerset2 element t)
;;

let rec powerset list = 
  match list with 
    [] -> [[]]
  | h::[] -> [[];[h]]
  | h::t -> powerset2 h (powerset t)
;;

ちなみに、実行すると、

# powerset [1;2;3];;
- : int list list = [[]; [1]; [2]; [1; 2]; [3]; [1; 3]; [2; 3]; [1; 2; 3]]
# powerset ["egg"; "sausage"; "spam"];;
- : string list list =
[[]; ["egg"]; ["sausage"]; ["egg"; "sausage"]; ["spam"]; ["egg"; "spam"];
 ["sausage"; "spam"]; ["egg"; "sausage"; "spam"]]

となって、確かにべき集合を求めることが出来た