set -集合型

【　目次　】

pythonの型については「型についてのあれこれ」で既に述べているのだけれども、駆け足でいってしまったので、機会があれば都度，捕捉していきた。

pythonには集合型がサポートされている。
集合の数学的概念については

高等学校数学A/集合と論理 - Wikibooks

集合型はsetとかfrozensetというクラスになる。
setとfrozensetの違いは、listとtupleの違いのようにfrozensetの場合には要素を変更する事ができない(イミュータブル)。

集合型の定義

集合(set型)の定義は要素を辞書のように波括弧｛｝で囲む。

set_var = {1,2,3};

上記の集合型の変数を表示してみる。

print set_var

実行結果

set([1, 2, 3])

frozenset型にはこのような表記法は無い。 frozenset型のオブジェクトを定義する場合には次項で述べるfrozenset型のコンストラクタを使う。

空の集合の定義と集合のコンストラクタ

空の集合を定義するのに、以下のように空の波括弧を使用してはならない。

set_var = {};

上記のコードは、空の辞書を定義していると解釈されるようだ。

print set_var, type(set_var)

実行結果

{} <type 'dict'>

空の集合を定義するには、空の波括弧では無くsetクラスのコンストラクタを使う。

set_var = set();
print set_var, type(set_var)

実行結果

set([]) <type 'set'>

要素1,2,3を要素に持つ集合はsetクラスのコンストラクタを用いて

set_var=set(1,2,3)

としてはならない。

実行結果

TypeError: set expected at most 1 arguments, got 3

コンストラクタの引数は１個でなければならない、と怒られてしまう。
setクラスのコンストラクタの引数にはiterableなオブジェクトを指定する。

iterableなオブジェクトとは何かというと

用語集 — Python 2.7.x ドキュメント

イテレータプロトコルを実装した型のオブジェクトという事だろう、多分。

プロトコルというのは規約とか約束事という意味があり

プロトコル - Wikipedia

プロトコルまたはプロトコール（英語 protocol 英語発音: [ˈproutəˌkɔːl] プロウタコール、[ˈproutəˌkɔl] プロウタコル、フランス語 protocole フランス語発音: [prɔtɔkɔl] プロトコル）とは、複数の者が対象となる事項を確実に実行するための手順等について定めたもの。
...
情報工学分野でマシンやソフトウェア同士のやりとりに関する概念を指すためにも用いられるようになった。

イテレータプロトコルの場合でいうと、「イテレータとジェネレータ」で述べたとおり、__iter__メソッドとnextメソッドが実装されている型という事になる。

もちろん、pythonのシーケンス型や辞書型などのいわゆるコンテナ型とかコレクション型とかいわれているクラスはイテレータを実装しており、setクラスのコンストラクタの引数として使う事ができる。

# set_var = set(1, 2, 3) # error

# タプルよりset型を生成
set_var = set((1, 2, 3)); print set_var
tpl = (1, 2, 3); set_var = set(tpl); print set_var
# リストよりset型を生成
lst = [1, 2, 3]; set_var = set(lst); print set_var

# setよりset型を生成
set_var = set({1, 2, 3}); print set_var

# 辞書型を渡すと、キーがセットに格納
dic = {"key1" : "value1", "key2" : "value2"}; set_var = set(dic); print set_var

# 文字列よりset型を生成
set_var = set("abc"); print set_var

実行結果

set([1, 2, 3])
set([1, 2, 3])
set([1, 2, 3])
set([1, 2, 3])
set(['key2', 'key1'])
set(['a', 'c', 'b'])

辞書型をset型のコンスタラクタに渡すと、辞書のキーが集合の要素として格納される点に注意。

コンスタラクタは、見方を変えると型変換の関数という事もできる。

frozenset型の生成例も以下に示す。

lst=[1,2,3]; f=frozenset(lst); print f
tpl=(1,2,3); f=frozenset(tpl); print f
dic={"key1" : "value1","key2" : "value2"}; f=frozenset(dic); print f

実行結果

frozenset([1, 2, 3])
frozenset([1, 2, 3])
frozenset(['key2', 'key1'])

辞書のキーや集合の要素には変更可能なオブジェクトを指定する事ができない

公式ドキュメントによると

set および frozenset という、2つの組み込みset型があります。 set は変更可能な — add() や remove() のようなメソッドを使って内容を変更できます。変更可能なため、ハッシュ値を持たず、また辞書のキーや他のsetの要素として用いることができません。 frozenset 型はイミュータブルで、ハッシュ化可能 (hashable) です — 作成後に内容を改変できません。そのため、辞書のキーや他の集合の要素として使えます。

これって、どういう意味？
ネットでググッてみたら

Python における hashable - Qiita

自分なりに整理してみると。

変更可能なオブジェクトである辞書型やリスト型，set型は、ミュータブル(mutable)と呼ばれる。
これに対して、変更できないタプルやfrozensetはイミュタブル(immutable)と呼ばれる。
変更可能なオブジェクトはハッシュ値を持たないが、変更できないイミュタブルなオブジェクトはハッシュ値を持つ。
辞書のキーやset型の要素には、ハッシュ値を持たない変更可能なオブジェクトを指定する事ができない。

ミュータブルとかイミュタブルというのは、

ハッシュ値はコレクション型の中の要素をすばやく探すための値となるもので、

ハッシュ関数 - Wikipedia

ハッシュ値を持つオブジェクトは、__hash__メソッドを持っている。
そして、__hash__メソッドはオブジェクトのハッシュ値が必要になった時に、組込み関数hash などから呼びだされる。

一部の組込み型には、ハッシュ値を持たないオブジェクト(list，bytearray，set，dictorionary)が存在する。
文字列型やユーザ定義のクラスやそのインスタンスはハッシュ値を持つ。

これらの事を確認してみよう。
例えば、

lst=[1,2,3]
dic={lst:"value"}

は辞書のキーがハッシュ値を持たないリスト型のためエラーになる。

実行結果

TypeError: unhashable type: 'list'

しかし、キーにリスト型のかわりにハッシュ値を持つタプル型を指定すればエラーにならない。

tpl=(1,2,3)
dic={tpl:"value"}

ややこしい事に、すべてのタプル型が辞書型のキーに成りうるかというと、タプルの要素にミュータブルな要素が格納されている場合はキーになれない。

tpl=(1,[2,3],4)
print tpl
dic={tpl:"value"}

エラーになってしまう。

実行結果

TypeError: unhashable type: 'list'

集合型の場合も同様に、要素に変更可能な(ハッシュ値を持たない)集合を指定したり

set_var = {1, {2, 3}, 4}

リストを指定すると

set_var = {1, [2, 3], 4}

エラーになる。
frozensetの場合も同じである。

fset = frozenset([1, {2, 3}, 4])
fset = frozenset([1, [2, 3], 4])

上記の２行のコードはどちらの行もラーになってしまう。

実行結果

TypeError: unhashable type: 'set'

しかし変更できない（ハッシュ値を持つ）frozensetやタプルを要素として指定する事はできる。

set_var = {1, frozenset({2, 3}), 4}
print set_var
set_var = {1, (2, 3), 4}
print set_var

fset = frozenset({1, frozenset({2, 3}), 4})
print fset
fset = frozenset({1, (2, 3), 4})
print fset

上記のコードではエラーは発生しない。

実行結果

set([1, frozenset([2, 3]), 4])
set([(2, 3), 4, 1])
frozenset([1, frozenset([2, 3]), 4])
frozenset([4, (2, 3), 1])

ハッシュ値を持たないとはどういう事かというと、特別な場合を除くと、オブジェクトが__hash__属性を持っていて、かつその__hash__属性が呼び出し可能(callable)。
リストや辞書，set型は__hash__属性を持っている。

lst = [1, 2, 3]
set_var = {1, 2, 3}
dic = {"key1":"value1", "key2":"value2"}

print hasattr(lst, "__hash__")
print hasattr(dic, "__hash__")
print hasattr(set_var, "__hash__")

実行結果

True
True
True

しかし、この__hash__属性は、呼び出し可能(callable)ではない。
呼び出し可能かどうかをcallable関数で確認してみる。

print callable(lst.__hash__)
print callable(dic.__hash__)
print callable(set_var.__hash__)

実行結果

False
False
False

このため、辞書のキーにしたり、集合の要素にする事はできない。

set_vae2 = {1, lst, 3}
set_vae2 = {1, dic, 3}
set_vae2 = {1, set_var, 3}

上記のコードはすべてエラーになる。

実行結果

TypeError: unhashable type: 'set'

これに対して、タプルやfrozenset，文字列型や新スタイルのユーザ定義のクラスやクラスのインスタンスはハッシュ値を持つ。
「新スタイルのクラスと旧スタイルのクラス」については

新スタイルのクラスと旧スタイルのクラス - 愚鈍人

tpl = (1, 2, 3)
fset = frozenset((1, 2, 3))
s = "abc"

class NewCls(object):
    pass
new_inst = NewCls()

print hasattr(tpl, "__hash__") & callable(tpl.__hash__)
print hasattr(fset, "__hash__") & callable(fset.__hash__)
print hasattr(s, "__hash__") & callable(s.__hash__)
print hasattr(NewCls, "__hash__") & callable(NewCls.__hash__)
print hasattr(new_inst, "__hash__") & callable(new_inst.__hash__)

実行結果

True
True
True
True
True

そして、辞書のキーにしたり、集合の要素にする事ができる。

set_vae2 = {1, tpl, 3}
set_vae2 = {1, fset, 3}
set_vae2 = {1, s, 3}
set_vae2 = {1, NewCls, 3}
set_vae2 = {1, new_inst, 3}

上記の集合の定義のコードは、すべて有効である。

python2の旧スタイルのクラスの場合はどうかというと

class OldCls:
    pass
old_inst=OldCls()

print hasattr(OldCls, "__hash__")
print hasattr(old_inst, "__hash__")

旧スタイルのクラスでは__hash__属性そのものを保持していないようだ。

実行結果

False
False

しかし、旧スタイルのクラスの場合には、__hash__属性が定義されていないにもかかわらず、特別にハッシュ値を取得できるようで。

print hash(OldCls)
print hash(old_inst)

hash関数によりハッシュ値を取得できる。

実行結果

1955458
2430996

このため、以下のコードはすべて有効となるようだ。

set_vae2 = {1, OldCls, 3}
set_vae2 = {1, old_inst, 3}

Pythonのタプルについて(三度目) - 西尾泰和のはてなダイアリー

A: 一言で説明すると「『変更可能だからハッシュ値を計算できず辞書のキーにすることができない』という説明は厳密には正しくない」となる。たとえばlistを継承してハッシュ関数を定義すれば変更可能なまま辞書のキーにすることが可能になるし、ユーザ定義のクラスのインスタンスはデフォルトのハッシュ関数を継承するので辞書のキーにすることができる。Pythonのリストが辞書のキーにできないのは「技術的に不可能」なのではなく「意図的に禁止してある」のだ。

listのようにhash値を持たないオブジェクトでも、listクラスを継承して強引に__hash__メソッドを定義してやると、集合の要素に指定できるようになる。
このようなコードは感心できないが...

class MyList(list):
    def __hash__(self):
        return 99
my_lst=MyList([1,2,3])

set_var2 = {1, my_lst, 3}
print set_var2

実行結果

set([[1, 2, 3], 1, 3])

本来、「コレクションが書き込み可能かどうか」という事と「コレクション型の中の要素を高速に検索するためにハッシュ値を持つ」という事は別の事であるが、python内部の実装上の都合から「書き込み可能なコレクション型のオブジェクトはハッシュ値を持たない」という仕様になっていて、さらに、「辞書のキーやset型の要素にハッシュ値を持たない変更可能なオブジェクトを指定する事ができない」という制限が課せられているという事のようだ。

集合型の操作

要素の追加

set型への要素の追加はaddメソッドを使って

set_var={1,2,3}
set_var.add(99)
print set_var

実行結果

set([99, 1, 2, 3])

もちろん、変更不能のfrozenset型では、addメソッドなどの要素を変更してしまうメソッドは使用できない。

コレクション要素の追加

updateメソッドにより、コレクション型に含まれる複数の要素を集合に追加する事ができる。

まずは、集合に集合の要素を追加

set_var = {1, 2, 3}
set_var.update({3, 101, 102, 103})
print set_var

set([1, 2, 3, 101, 102, 103])

重複する要素は除かれる。

他のコレクション型の要素も追加してみる。

set_var = {1, 2, 3}
lst = [3, 101, 102, 103]
set_var.update(lst)
print set_var

set_var = {1, 2, 3}
dic = {"key1":"value1", "key2":"value2"}
set_var.update(dic)
print set_var

実行結果

set([1, 2, 3, 101, 102, 103])
set([1, 2, 3, 'key1', 'key2'])

文字列を追加すると、予想に反して

set_var = {1, 2, 3}
s = ["abcd"]
set_var.update(s)
print set_var

文字に分解されずに、文字列全体が１つの要素として追加される。

実行結果

set(['abcd', 1, 2, 3])

文字列が１つの要素として追加できるならと調子にのって単一の値を追加してみると。

set_var = {1,2,3}
set_var.update(99)

実行結果

TypeError: 'int' object is not iterable

「int型はiterableなオブジェクトでは無い」と怒られた。

要素の削除

要素の削除はremoveメソッド

set_var.remove(99)
print set_var

実行結果

set([99, 2, 3])

含まれない要素を削除するとエラーが発生。

set_var.remove("xxx")

KeyError: 'xxx'

要素の削除にはもう１つのメソッドdiscardがあり、こちらは含まれない要素を削除してもエラーは発生しない。

set_var={1,2,3,99}
set_var.discard(99)
print set_var
set_var.discard("xxx")
print set_var

実行結果

set([3, 1, 2])
set([3, 1, 2])

要素の取り出し

popメソッドにより、任意の要素を集合から取り出す事ができる。
popメソッドにより取り出された要素は、集合から削除される。
集合が空であれば、KeyErrorが送出される。

次のコードは、集合が空になるまで集合の要素を取り出して表示する。

set_var = {1, 2, 3, 99}
try:
    while True:
        x = set_var.pop()
        print x, set_var
except KeyError:
    pass

実行結果

3 set([1, 2, 99])
1 set([2, 99])
2 set([99])
99 set([])

集合も、他のコレクション型と同じくfor文を使って要素を取り出す事ができる。
for文の場合には、もちろんpopメソッドと異なり取り出された要素は集合から削除されない。

set_var = {1, 2, 3, 99}
for x in set_var:
    print x, set_var

print set_var

実行結果

3 set([3, 1, 2, 99])
1 set([3, 1, 2, 99])
2 set([3, 1, 2, 99])
99 set([3, 1, 2, 99])

集合に要素が含まれているかの確認

集合に要素が含まれているかの確認するには、in演算子を使って

set_var = {1,2,3}
x=2
if x in set_var:
    print "set_varに2が含まれる"
else:
    print "set_varに2が含まれない"

実行結果

set_varに2が含まれる

要素が含まれていないかの確認にはnot in

if x not in set_var:
    print "set_varに2が含まれない"
else:
    print "set_varに2が含まれる"

要素が含まれているかの確認には__contains__メソッドを使う事もできるようだ。

if set_var.__contains__(x):
    print "set_varに2が含まれる"
else:
    print "set_varに2が含まれない"

部分集合の確認

部分集合の確認にはin演算子は使えない。
これはダメ!

set_var = {1,2,3}
if {2,3} in set_var:
    print "set_varに2と3が含まれる"
else:
    print "set_varに2と3が含まれない"

実行結果

set_varに2と3が含まれない

上記のコードは、集合の要素の中に入れ子で2と3の集合が含まれているか、確認する事になる。

set_var = {1,frozenset({2,3}),3}
if {2,3} in set_var:
    print "set_varに2と3の集合が含まれる"
else:
    print "set_varに2と3の集合が含まれない"

実行結果

set_varに2と3の集合が含まれる

部分集合の確認にはissubsetメソッドやissupersetメソッドを使う。これが正しい

set_var = {1,2,3}
if {2,3}.issubset(set_var):
    print "set_varに2と3が含まれる"
else:
    print "set_varに2と3が含まれない"

または

if set_var.issuperset({2,3}):
    print "set_varに2と3が含まれる"
else:
    print "set_varに2と3が含まれない"

実行結果

set_varに2と3が含まれる

部分集合の確認には不等号を使う事もできる。

if {2, 3} <= set_var:
    print "set_varに2と3が含まれる"
else:
    print "set_varに2と3が含まれない"

共通の要素を持たないかどうかの確認

isdisjointメソッドを使って、２つの集合が共通の要素を持たないかどうかを知る事ができる。
共通の要素を持たない場合に、isdisjointメソッドはTrueを返す。

set_var = {1, 2, 3}
print set_var.isdisjoint({3, 4, 5})

実行結果

False

要素をぜんクリ

集合を空にするにはclearメソッドを使う。

set_var.clear()
print set_var

実行結果

set([])

要素をコピー

copyメソッドを使って集合をコピーする事ができる。

set_var = {1, 2, 3}
set_var2 = set_var.copy()
print set_var2

実行結果

set([1, 2, 3])

copyメソッドは浅いコピー(シャローコピー)となる。

従って

class Person(object):
    def __init__(self, name, age):
        self._name = name
        self._age = age

    def __repr__(self):
        return "name={0} , age={1}" .format(self._name,self._age)

set_var = {Person("gudon", 999), Person("foo", 10), Person("bar", 10)}
set_var2 = set_var.copy()
print set_var2

実行結果

set([name=foo , age=10, name=gudon , age=999, name=bar , age=10])

のような場合に、コピー元の要素の属性を変更すると、コピー先の要素の属性も変更されてしまう事になる。

for person in set_var:
    person._age += 5

print set_var2

set([name=foo , age=15, name=gudon , age=1004, name=bar , age=15])

要素数を取得

要素数を求めるには組込み関数len を

set_var = {1,2,3}
print len(set_var)

実行結果

集合演算

以下のような２つの集合の演算は

a={1,2,3}
b={3,4,5}

集合の結合（和集合A ∪ B）

2つの集合の結合するにはunionメソッドを使うか

print a.union(b)

または　|演算子を使って

print a | b

実行結果

set([1, 2, 3, 4, 5])

集合の共通部分（積集合A ∩ B）

共通部分の集合を求めるにはintersectionメソッドを使うか

print a.intersection(b)

または　&演算子を使って

print a & b

実行結果

set([3])

共通部分の集合は和集合とも呼ばれ

一方だけに含まれる要素の集合（排他的論理和A ⊕ B）

一方だけに含まれる要素の集合求めるにはsymmetric_differenceメソッドを使うか

print a.symmetric_difference(b)

もしくは、^演算子を使って

print a ^ b

実行結果

set([1, 2, 4, 5])

集合から別の集合に含まれる要素を削除（差集合A - B）

差集合 - Wikipedia

集合から別の集合に含まれる要素を削除するにはdifferenceメソッドを使うか

print a.difference(b)

もしくは、-演算子を使って

print a - b

実行結果

set([1, 2])

ちなみに、差集合を求めるのに-演算子が使えるからといって、和集合を求めるのに+演算子は用いる事は許されない。

print a + b

サポートされている演算子では無いと、エラーになってしまう。

実行結果

TypeError: unsupported operand type(s) for +: 'set' and 'set'

同様に、積集合にだからといってa * bも許されない。

andやorを使うと

2つの集合にandやorを使うと、どうなるのだろうか？

print a or b
print a and b

実行結果

set([1, 2, 3])
set([3, 4, 5])

orの場合は、左側に指定した集合が、andの場合には右側の集合が返るようだ。確認の為に右と左を逆にしてみると

print b or a
print b and a

実行結果

set([3, 4, 5])
set([1, 2, 3])

でも、これってどう解釈したらいいのだろう?

メソッドと演算子の違い

メソッドの場合には、他のコレクション型の値を引数として集合演算をおこなう事ができる。
以下のように、集合とリストに対して、

a = {1, 2, 3}
b_list = [3, 4, 5]

和集合の場合を例にとると、unionメソッドの引数にリスト型のオブジェクトを指定して、

print a.union(b_list)

集合とリストとの演算をおこなう事ができる。

実行結果

set([1, 2, 3, 4, 5])

これに対して、演算子の場合には、リストを指定すると

print a | b_list

エラーになってしまう。

実行結果

TypeError: unsupported operand type(s) for |: 'set' and 'list'

演算子を使う場合には、いったん、集合型に変換した後に、演算をおこなう必要がある。

print a | set(b_list)

実行結果

set([1, 2, 3, 4, 5])

集合の内包表記

リストの内包表記で述べたように、リストより新たなリストを生成できる。

vec = [2, 4, 6]
print [3*x for x in vec]

実行結果

[6, 12, 18]

リストの内包表記の角括弧［］を波括弧｛｝に修正する事で、内包表記を用いて新たな集合を生成する事ができる。

print {3*x for x in vec}

実行結果

set([18, 12, 6])

上記のコードはリストより集合を生成する例であるが、集合より新たな集合を生成する事もできる。

set_var = {2, 4, 6}
print {3*x for x in set_var}

実行結果

set([18, 12, 6])

if文を使って処理対象の集合要素の絞り込みも

print {3*x for x in set_var if x>3}

実行結果

set([18, 12])

もっともっと、いろいろな事が

print {abs(x * y) for x in set_var for y in {4, 3, -9}}

リストと違って重複する要素は除いてくれる。

実行結果

set([36, 6, 8, 12, 16, 18, 54, 24])

setsモジュール

以前は集合型を扱うsetsモジュールがあったが現在は撤廃されているもよう。

8.7. sets — ユニークな要素の順序なしコレクション — Python 2.7.x ドキュメント

集合なんてどうせ使わないからとさらっと飛ばしていたが、いざ調べてみるとけっこう変なとこで想いもかけないハマリドコロがあって。