集合の演算と包除原理

集合とは、はっきり決まったものの集まりです。和集合や共通部分を使うと、「2つのサークルの、どちらかに入っている人は何人か」のような数を、重ねて数えずに求められます。

軽音楽サークルが25人、写真サークルが18人でも、合わせて43人とは限りません。両方に入っている人がいるからです。今日はその数え方を、表で学びます。

集合は、入るかどうかがはっきり決まるものの集まりです。入っている1つ1つを要素と呼び、{1, 2, 3} のように波かっこで書きます。

集合では、並べる順序は関係なく、同じ要素を2回数えません。{1, 2, 3} と {3, 2, 1} と {1, 1, 2, 3} は、すべて同じ集合です。

2つの集合 A と B を考えます。和集合は、A か B の少なくとも一方に入る要素の集合です。共通部分は、両方に入る要素の集合です。差集合は、A に入って B に入らない要素の集合です。

言いかえると、和集合は「または」、共通部分は「かつ」です。差集合は「A に入る、かつ B に入らない」です。前回の表と同じ形をしています。

python3 -c "A = {1, 2, 3, 4}; B = {3, 4, 5}; print(sorted(A | B), sorted(A & B), sorted(A - B))"

行を要素と考えます。2つの名簿をつなげて sort -u に渡すと、重なりを1回にした和集合になります。

sort の後ろに uniq -d をつなぐと、2回出てきた行だけが残ります。つまり両方の名簿にある行、共通部分です。ただし、各名簿に同じ名前が1回ずつしかない場合に限ります。

printf "1\n2\n3\n4\n3\n4\n5\n" | sort -u

printf "1\n2\n3\n4\n3\n4\n5\n" | sort | uniq -d

# 名簿 a の全員を入れ、b からは、まだいない人だけを足します。
a = [1, 2, 3, 4]
b = [3, 4, 5]
union = []
for x in a:
    union.append(x)
for x in b:
    if x not in union:
        union.append(x)
print(union)
# if の行を消すと、3 と 4 が2回出ます。試してみましょう。

包除原理は、2つの集合を合わせた数を、重なりを引いて求める決まりです。(A の人数) + (B の人数) - (両方の人数) で求めます。

両方に入る人は、足すときに2回数えられています。1回分を引けば、ちょうど1回ずつになります。

python3 -c "print(25 + 18 - 7, 25 - 7, 18 - 7)"

3つの集合では、3つの重なりを引いたあと、3つ全部の重なりを1回足し戻します。引きすぎるからです。

A が20、B が15、C が10、A と B が6、A と C が4、B と C が3、3つ全部が2のとき、和集合の大きさを求めましょう。