suzu6はじめに
Pythonを勉強するため、東京工業大学の岡崎教授が出題されている言語処理100本ノック 2015を解いていきます。
より深く理解するため、別解や利用したライブラリの解説もまとめていきます。
環境
Python3.6
OS : mac
問題
06. 集合
"paraparaparadise"と"paragraph"に含まれる文字bi-gramの集合を，それぞれ, XとYとして求め，XとYの和集合，積集合，差集合を求めよ．さらに，'se'というbi-gramがXおよびYに含まれるかどうかを調べよ．
集合演算
参考 Python, set型で集合演算（和集合、積集合や部分集合の判定など）
参考というか、まんま答えにたどり着いてしまったのですが、上記のリンクを参考にしています。
集合は要素の集まりです。重複する要素はありません。重複を許した場合は多重集合となります。
解答
x_str = "paraparaparadise"
y_str = "paragraph"
def n_gram(sentence, N):
"""
文字のn-gramを返す。
"""
result = []
for it in range(len(sentence)):
if it + N > len(sentence):
return result
result.append(sentence[it: it+N])
X = set(n_gram(x_str, N=2))
Y = set(n_gram(y_str, N=2))
print(X)
# => {'is', 'se', 'ad', 'di', 'ap', 'ar', 'pa', 'ra'}
print(Y)
# => {'ph', 'gr', 'ra', 'ap', 'ar', 'pa', 'ag'}
# 和集合
_sum = X | Y
print(_sum)
# => {'ar', 'ad', 'is', 'ag', 'pa', 'ap', 'ph', 'ra', 'gr', 'di', 'se'}
# 積集合
_intersection = X & Y
print(_intersection)
# => {'ra', 'ap', 'pa', 'ar'}
# 差集合
_diff_X = X - Y
_diff_Y = Y - X
print(_diff_X)
# => {'is', 'se', 'di', 'ad'}
print(_diff_Y)
# => {'ag', 'gr', 'ph'}
# `se`を含むか
print('se' in X)
# => True
print('se' in Y)
# => False
解説
Pythonには集合を扱うset型が用意されています。
4.9. set（集合）型 — set, frozenset
set型には集合演算も標準で付いているため、今回はこれを利用しました。
X = set(n_gram(x_str, N=2))
Y = set(n_gram(y_str, N=2))
print(X)
# => {'is', 'se', 'ad', 'di', 'ap', 'ar', 'pa', 'ra'}
print(Y)
# => {'ph', 'gr', 'ra', 'ap', 'ar', 'pa', 'ag'}
n-gram()で計算したbi-gramをset()で集合に変換しています。
n-gramは前回作成した関数を使います。
set型は{}で囲まれ、要素の順序は不定となります。
和集合
和集合は２つの集合をくっつけた集合です。
|演算子またはset.union()で求めることが出来ます。
# 和集合
_sum = X | Y
print(_sum)
# => {'ar', 'ad', 'is', 'ag', 'pa', 'ap', 'ph', 'ra', 'gr', 'di', 'se'}
もしくは
# 和集合
_sum = X.union(Y)
積集合
積集合は２つの集合の共通分を抜き出した集合です。
&演算子またはset.intersection()で求めることが出来ます。
# 積集合
_intersection = X & Y
print(_intersection)
# => {'ra', 'ap', 'pa', 'ar'}
もしくは
# 積集合
_intersection = X.intersection(Y)
差集合
差集合は別の集合に含む要素を除いた集合です。
-演算子またはset.difference()で求めることが出来ます。
# 差集合
_diff_X = X - Y
_diff_Y = Y - X
print(_diff_X)
# => {'is', 'se', 'di', 'ad'}
print(_diff_Y)
# => {'ag', 'gr', 'ph'}
もしくは
_diff_X = X.difference(Y)
部分集合
'se'というbi-gramがXおよびYに含まれるかどうか
要素が集合に含まれているかはinを使って判定できます。
# `se`を含むか
print('se' in X)
# => True
print('se' in Y)
# => False
また、ある集合を含むかを調べる場合は、<=を使います。
print({'se', 'ap'} <= X)
# => True
print({'se', 'ap'} <= Y)
# => False
print(X - Y <= X)
# => True
終わりに
set型の使い方を一通り覚えることができました。 集合の扱いを簡単な演算子でできるのは大変便利です。
続いての記事
前の問題：03. 円周率
次の問題：06. 集合