「集合」をプログラムに落とし込む

最近数学にとてつもなくハマり、勉強をするようになりました。今まで黙々と勉強をしていたのですが、「せっかくなら勉強した内容をプログラムに落とし込んだらいいのでは？」という考えにいたりました。その方が、定着度も上がるだろうし、普段行なっているプログラミングにも数学の知識が活きやすくなると思ったのです。

というわけで、吸収した数学知識を徐々にプログラムに落とし込んでいきます。今回は「集合」。言語はPythonです。

集合

対象としているものの集まりのうち、対象物が属しているか属していないかが、明確に判定できる集まりを集合という。

集合を構成しているものを要素、または元という。明示方法としては、列挙と条件が挙げられる。

列挙

A={1,2,3,4,5}

条件

A={n|1<=n<=5、nは自然数}

といった感じ。

要素数が少なければ列挙で明示できますが、多くなると条件式で表されることが多いです。

Pythonで集合を表現

Pythonには、集合を扱うためのデータ構造があります。

{}やset()を使用します。

#{}で生成
fruits = {'apple', 'banana', 'orange', 'grape', 'melon'}

#set()で生成
fruits = set(['apple', 'banana', 'orange', 'grape', 'melon'])

対象としているもの全体を全体集合といいます。また、要素を一つも持たない集合を空集合といいます。

そして、ある集合に含まれる集合のことを部分集合と言います。

例えば、集合Aの要素が集合Bの要素でもある時、AはBの部分集合といえる。

$A \subset B$

#AはBの部分集合である
A = {1,2,3,4,5}
B = {1,2,3,4,5,6,7,8,9,10}

>>> A <= B
True

Pythonで集合演算

次はPythonで集合演算をしてみる。

集合サンプルとして、アニメ好きなAくん、Bくん、Cさんの３人を用意する。３人にはあるアニメリストからオススメのアニメを5個ずつ答えてもらったとする。

＜アニメリスト＞

シュタインズゲート
ソードアートオンライン
銀魂
PSYCHO-PASS
NEW GAME!
SHIROBAKO
化物語
魔法少女まどか☆マギカ
メイドインアビス
涼宮ハルヒ憂鬱
四月は君の嘘
幼女戦記

＜全体集合と３人の回答(集合)＞

#全体集合
U = {'シュタインズゲート', 'ソードアートオンライン', 'PSYCHO-PASS', '銀魂', 'NEW GAME!', 'SHIROBAKO', '化物語', '魔法少女まどか☆マギカ', 'メイドインアビス', '涼宮ハルヒの憂鬱', '四月は君の嘘', '幼女戦記'}
#Aくん
A = {'シュタインズゲート', 'ソードアートオンライン', 'PSYCHO-PASS', '銀魂', 'NEW GAME!'}
#Bくん
B = {'NEW GAME!', 'SHIROBAKO', '銀魂', 'ソードアートオンライン', '化物語'}
#Cさん
C = {'化物語', '魔法少女まどか☆マギカ', '銀魂', 'メイドインアビス', '涼宮ハルヒの憂鬱'}

このサンプルを使用して集合演算をしていきます。

ベン図

ベン図で表すと以下の通り。

ベン図

和集合

$A \cup B$

#AとBの和集合(A or B or both)
>>> A | B
{'NEW GAME!', 'シュタインズゲート', '化物語', 'SHIROBAKO', 'ソードアートオンライン', 'PSYCHO-PASS', '銀魂'}

$B \cup C$

#BとCの和集合(B or C or both)
>>> B | C
{'NEW GAME!', '魔法少女まどか☆マギカ', 'メイドインアビス', '化物語', 'SHIROBAKO', '涼宮ハルヒの憂鬱', 'ソードアートオンライン', '銀魂'}

$C \cup A$

#CとAの和集合(C or A or both)
>>> C | A
{'NEW GAME!', 'シュタインズゲート', '魔法少女まどか☆マギカ', 'メイドインアビス', '化物語', 'ソードアートオンライン', 'PSYCHO-PASS', '銀魂', '涼宮ハルヒの憂鬱'}

積集合

$A \cap B$

#AとBの積集合(both A and B)
>>> A &amp; B
{'銀魂', 'ソードアートオンライン', 'NEW GAME!'}

$B \cap C$

#BとCの積集合(both B and C)
>>> B &amp; C
{'銀魂', '化物語'}

$C \cap A$

#CとAの積集合(both C and A)
>>> C &amp; A
{'銀魂'}

$A \cap B \cap C$

#AとBとCの積集合(all of A and B and C)
>>> A &amp; B &amp; C
{'銀魂'}

差集合

$A \setminus B$

#AとBの差集合(A but not in B)
>>> A - B
{'PSYCHO-PASS', 'シュタインズゲート'}

$B \setminus C$

#BとCの差集合(B but not in C)
>>> B - C
{'NEW GAME!', 'ソードアートオンライン', 'SHIROBAKO'}

$C \setminus A$

#CとAの差集合(C but not in A)
>>> C - A
{'魔法少女まどか☆マギカ', 'メイドインアビス', '化物語', '涼宮ハルヒの憂鬱'}

対称差集合

#AとBの対称差集合(A or B but not both)
>>> A ^ B
{'化物語', 'PSYCHO-PASS', 'シュタインズゲート', 'SHIROBAKO'}

#BとCの対称差集合(B or C but not both)
>>> B ^ C
{'涼宮ハルヒの憂鬱', 'NEW GAME!', 'ソードアートオンライン', 'SHIROBAKO', '魔法少女まどか☆マギカ', 'メイドインアビス'}

#CとAの対称差集合(C or A but not both)
>>> C ^ A
{'涼宮ハルヒの憂鬱', '化物語', 'NEW GAME!', 'PSYCHO-PASS', 'シュタインズゲート', 'ソードアートオンライン', '魔法少女まどか☆マギカ', 'メイドインアビス'}

#AとBとCの対称差集合(A or B or C but not all)
>>> A ^ B ^ C
{'銀魂', '涼宮ハルヒの憂鬱', 'PSYCHO-PASS', 'シュタインズゲート', 'SHIROBAKO', '魔法少女まどか☆マギカ', 'メイドインアビス'}

補集合

$\overline{ A }$

#Aの補集合(not in A)
>>> U - A
{'化物語', '涼宮ハルヒの憂鬱', 'メイドインアビス', '魔法少女まどか☆マギカ', 'SHIROBAKO', '四月は君の嘘', '幼女戦記'}

$\overline{ B }$

#Bの補集合(not in B)
>>> U - B
{'シュタインズゲート', '涼宮ハルヒの憂鬱', 'PSYCHO-PASS', 'メイドインアビス', '魔法少女まどか☆マギカ', '四月は君の嘘', '幼女戦記'}

$\overline{ C }$

#Cの補集合(not in C)
>>> U - C
{'シュタインズゲート', 'ソードアートオンライン', 'PSYCHO-PASS', 'SHIROBAKO', 'NEW GAME!', '四月は君の嘘', '幼女戦記'}

番外編

ド・モルガンの法則

ついでにド・モルガンの法則が本当に成り立っているのかどうかをプログラムで確認してみましょう。

$\overline{ A \cap B } = \overline{ A } \cup \overline{ B }$

#全体集合
U = {'シュタインズゲート', 'ソードアートオンライン', 'PSYCHO-PASS', '銀魂', 'NEW GAME!', 'SHIROBAKO', '化物語', '魔法少女まどか☆マギカ', 'メイドインアビス', '涼宮ハルヒの憂鬱', '四月は君の嘘', '幼女戦記'}
#Aくん
A = {'シュタインズゲート', 'ソードアートオンライン', 'PSYCHO-PASS', '銀魂', 'NEW GAME!'}
#Bくん
B = {'NEW GAME!', 'SHIROBAKO', '銀魂', 'ソードアートオンライン', '化物語'}

left = set(U - (A | B))
right = set(U - A) &amp; set(U - B)

print (left == right)

上記の出力結果はTrue。

$\overline{ A \cup B } = \overline{ A } \cap \overline{ B }$

#全体集合
U = {'シュタインズゲート', 'ソードアートオンライン', 'PSYCHO-PASS', '銀魂', 'NEW GAME!', 'SHIROBAKO', '化物語', '魔法少女まどか☆マギカ', 'メイドインアビス', '涼宮ハルヒの憂鬱', '四月は君の嘘', '幼女戦記'}
#Aくん
A = {'シュタインズゲート', 'ソードアートオンライン', 'PSYCHO-PASS', '銀魂', 'NEW GAME!'}
#Bくん
B = {'NEW GAME!', 'SHIROBAKO', '銀魂', 'ソードアートオンライン', '化物語'}

left = set(U - (A &amp; B))
right = set(U - A) | set(U - B)

print (left == right)

上記の出力結果もTrue。

したがって、ド・モルガンの法則は成り立っていることが確認できる。

Published 8 Nov 2017

Software Engineer, I love tech! anime!Yu-ki Tanaka on Twitter