3. 冪集合

著者:梅谷武

冪集合を生成する処理を実装する。

作成:2024-04-27
更新:2024-10-30

探索空間がある集合の冪集合となることがある。このようなときはすべての部分集合を構成する再帰やループを作り、各部分集合が条件を満たすかどうか調べることになる。すべての部分集合を構成して冪集合を生成する技法はこの種の問題を解くときの基本形を与える。

冪集合

集合Aの冪集合べきしゅうごう, power set(power set)とはAに含まれる部分集合全体の集合

P(A) := {X|X⊆A}

のことである。例えば集合{a,b}の部分集合は

{}, {a}, {b}, {a,b}

の四つであり、冪集合P({a,b})はこれらを元とする集合である。

P({a,b}) = {{}, {a}, {b}, {a,b}}

集合{a,b,c}の部分集合は

{}, {a}, {b}, {c}, {a,b}, {b,c}, {c,a}, {a,b,c}

の八つであり、冪集合P({a,b,c})はこれらを元とする集合である。ここですぐ気が付くように

P({a,b,c}) = P({a,b}) ∪ (c + P({a,b}))

c + P({a,b}) := {{c}, {c,a}, {c,b}, {c,a,b}}

となっている。このことから冪集合をリストのリストとして表現すると冪集合が再帰的に求められること、さらにはn元集合の冪集合の要素数は2ⁿになることがわかる。

3.2 添字集合

課題

自然数n＞0が与えられたとき、添字集合

{0, 1, ⋯, n－1}

をリストとして与え、その冪集合をリストのリストとして求める。

C++

powset.cpp:

#include <print>
#include <string>
#include <vector>
 
void print_subsets(std::vector<std::vector<int>> &subsets) {
  for (const auto &subset : subsets) {
    std::print("{{ ");
    for (const auto &num : subset)
      std::print("{} ", num);
    std::print("}}\n");
  }
}
 
std::vector<std::vector<int>> powerset(const std::vector<int> &set) {
  std::vector<std::vector<int>> result;
  const int len = set.size();
  for (int i = 0; i < (1 << len); ++i) {
    std::vector subset;
    for (int j = 0; j < len; ++j)
      if (i & (1 << j))
        subset.push_back(set[j]);
    result.push_back(subset);
  }
  return result;
}
 
int main(int argc, char *argv[]) {
  if (argc != 2) {
    std::println("Usage: powset <positive integer>");
    return 1;
  }
  int n = std::stoll(argv[1]);
  if (n < 1) {
    std::println("{} is not positive.", n);
    return 1;
  }
  std::vector<int> set;
  for (int i = 0; i < n; ++i)
    set.push_back(i);
  std::vector<std::vector<int>> powset = powerset(set);
  std::println("n = {}", n);
  std::println("size = {}", powset.size());
  // print_subsets(powset);
  return 0;
}

makefile:

CPPG = g++
CPPL = clang++
CPPFLAGS = -std=c++23 -O2
SRC = powset.cpp
EXES = powset_g powset_l
 
all: $(EXES)
 
powset_g: $(SRC)
	$(CPPG) $(CPPFLAGS) -o $@ $(SRC)
 
powset_l: $(SRC)
	$(CPPL) $(CPPFLAGS) -o $@ $(SRC)
 
clean:
	rm -f $(EXES)

n = 23で測定する。

$ measure ./powset_g 23
n = 23
size = 8388608
======================================
Process exited with status: 0
total time:  3.087909 [sec]
mem  size:     691380 [KB]
code size:        123 [KB]

$ measure ./powset_l 23
n = 23
size = 8388608
======================================
Process exited with status: 0
total time:  2.926025 [sec]
mem  size:     691216 [KB]
code size:         97 [KB]

OCaml

再帰かループかを決めるために両方作って比較した結果、再帰が有利であるという結論になった。このプログラムを書くにあたってこれまでに蓄積してきたノウハウが役立った。ここでまとめておく。

再帰の中に@演算を入れない。
→lst1@lst2の代わりに(List.rev_append (List.rev lst1) lst2)を使う。
try .. with ... では末尾再帰にならない。
→match式で処理することで末尾再帰最適化が行われる。
List.mapは末尾再帰でない。
→末尾再帰版mapを使う。
List.fold_rightは末尾再帰でない。
→List.fold_leftを用いてリストを反転して左畳み込みする。

powset.ml:

open Printf
 
let print_subsets subsets =
  List.iter (fun subset ->
    print_string "{ ";
    List.iter (fun num -> print_int num; print_string " ") subset;
    print_endline "}"
  ) subsets
 
let map f lst =
  let rec aux acc = function
    | [] -> List.rev acc
    | x :: xs -> aux (f x :: acc) xs
    in
    aux [] lst
  
let rec power_set set =
  match set with
    | [] -> [[]]
    | hd :: tl ->
        let rest = power_set tl in
        (List.rev_append (List.rev rest) (map (fun sub -> hd :: sub) rest))
 
let () =
  let len = Array.length Sys.argv in
  if len <> 2 then
    printf "Usage: powset <positive integer>\n"
  else
    let n = int_of_string (Sys.argv.(1)) in
    if n < 1 then
      printf "%d is not positive.\n" n
    else
      let set = List.init n (fun i -> i) in
      let powset = power_set set in
      printf "n = %d\n" n;
      printf "size = %d\n" (List.length powset)
      (* print_subsets powset *)

n = 23で測定する。

$ ocamlopt -O2 -o powset powset.ml
t$ measure ./powset 23
n = 23
size = 8388608
======================================
Process exited with status: 0
total time:  2.926571 [sec]
mem  size:     692372 [KB]
code size:       2364 [KB]

Racket

再帰かループかを決めるために両方作って比較した結果、再帰が有利であるという結論になった。

powset.rkt:

#lang racket
(require iso-printf)
 
(define (print-subsets subsets)
  (for ([subset subsets])
    (display "{ ")
    (for ([num subset])
      (display num)
      (display " "))
    (display "}")
    (newline)))
 
(define (power-set set)
  (cond
    [(empty? set) (list empty)]
    [else
      (let ([hd (car set)]
            [tl (cdr set)])
        (define rest (power-set tl))
        (append rest
          (map (λ (sub) (cons hd sub)) rest)))]))
 
(define (main args)
  (let ([len (vector-length args)]
        [n 0]
        [lst '()])
    (cond
      [(= len 1)
        (set! n (string->number (vector-ref args 0)))
        (cond
          [(> n 0)
            (define set (range n))
            (define powset (power-set set))
            (printf "n = %d\n" n)
            (printf "size = %d\n" (length powset))
            ;;(print-subsets powset)
            ]
          [else
            (printf "%d is not positive.\n" n)])]
      [else
        (printf "Usage: powset <positive integer>\n")])))
 
(main (current-command-line-arguments))

n = 23で測定する。

$ raco exe powset.rkt
$ measure ./powset 23
n = 23
size = 8388608
======================================
Process exited with status: 0
total time:  4.643602 [sec]
mem  size:     908676 [KB]
code size:      12444 [KB]

3.3 まとめ

測定結果を表にまとめる。単位は秒[sec]。

測定項目	GCC	Clang	OCaml	Racket
power set	3.088	2.926	2.927	4.644

語　　句

冪集合べきしゅうごう, power set

ある集合の部分集合全体から成る集合。

This document is licensed under the MIT License.
Copyright (C) 2024 Takeshi Umetani