はじめに
この記事は 数学オンチのプログラマが数学を学習し直すらしいですシリーズの「集合」についての記事です。
このシリーズは、
「まず数学記号を読めて、意味が理解できるようになろう」
「ついでにそれをソースコードで表せるようになろう」
が目標の、かなり小馬鹿にしたようなものとなります。
背景
集合、組合せ、それに伴う確率の問題は筆者は苦手である。
しかし、アルゴリズムの最大計算量や深層学習を学ぶ上では避けては通れない話である。
高校時代にベン図を書かれて「この条件に該当する人はここの範囲に入り……」
などと説明を受けてもピンとこなかった。更に居眠りグセがあり、自宅での復習もろくにしない筆者は、
集合の記号が途中で読めなくなって諦めた気がする。
本題
ということで、やっていこう
記号は覚えてます？
a \in A \\
A \subset B \\
こちら、上から
- 要素
aはAに 属する - 集合
Bは 集合Aを含む（部分集合）
ということだ。
「基本すぎるだろう」
って？ いや、自分は真面目に忘れていた。
せっかくなので一つPythonで書いてみよう。
fruit = {"apple", "banana", "tomato", "orange"} # 集合 `fruit` を定義
print("apple" in fruit) # `True` と表示されるはず。
Haskellだとこうかな？
import qualified Data.Set as Set
main :: IO ()
main = do
let fruit = Set.fromList ["apple", "banana", "tomato", "orange"]
putStrLn $ Set.showTree $ fruit
in 演算子で左辺が右辺の集合に属するか調べることができることがわかったと思う。
部分集合の表し方は今回省く。
論理和・論理積
こちらも記号が読めれば簡単にコードに落とし込める。
A \cap B \\
A \cup B
上から順番に、
- 集合
A, 集合Bどちらの条件にも属するもの（積集合） - 集合
Aもしくは集合Bまたはどちらの条件にも属するもの（和集合）
Pythonだとどう書くのだろうか。
fruit = {"apple", "banana", "tomato", "orange"} # 集合 `fruit` を定義
vegetables = {"eggplant", "tomato", "carrot", "broccoli"} # 集合 `vegetables` を定義
print(fruit.intersection(vegetables)) # 積集合なので、 `{"tomato"}` が表示されるはず。
print(fruit.union(vegetables)) # 和集合なので、 `{'tomato', 'apple', 'broccoli', 'carrot', 'banana', 'eggplant', 'orange'}` が表示されるはず。
ド・モルガンの法則
ここまで話すと、高校数学の難所「ド・モルガンの法則」が出てくる。
言われてもピンとこないと思うが、こういうことが成り立つらしい。
なお、上に線が引いてある部分は「〜ではない（否定）」の意味になる。
\overline{A \cap B} = \overline{A} \cup \overline{B} \\
\overline{A \cup B} = \overline{A} \cap \overline{B}
日本語にうまく直せない。
まとめ
- 最近のプログラミング言語は集合が扱えるかもよ（Pythonは標準で扱える）
- ド・モルガンの法則未だにわからないな……。
- そもそもド・モルガンの法則を考え初めてしまったのなら、分岐処理を分割したほうが良いかもしれない。
参考資料
P.S.
- Haskellのコード追加したい。
- ド・モルガンの法則の証明をしたい……。