【python】setのset

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
2014年7月23日追記
ImmutableSet
を使えばこんなめんどくさいことをしなくても良いことを知りました．
http://docs.python.jp/2/library/sets.html#sets.ImmutableSet
python3の場合はfrozenset
http://docs.python.jp/3.4/library/stdtypes.html#frozenset
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

Pythonにはsetという組み込みのデータ構造があります．
数学における集合を表現しており，組み込みのlistと似ていますが，
indexによる要素アクセスおよび重複する要素が許されません．
つまり，

l = [1,1,2,2,3,3]  # list
s = {1,1,2,2,3,3}  # set
# 重複要素は許されない：自動で排除される
print(l)  # [1,1,2,2,3,3]
print(s)  # {1,2,3}
# 重複要素を新たに追加しようとすると，エラーなしで自動的に排除される
l.append(3)
s.add(3)
print(l)  # [1,1,2,2,3,3,3]
print(s)  # {1,2,3}
# indexによる要素アクセスはできない
print(l[0])  # 1
print(s[0])  # TypeError: 'set' object does not support indexing

では，例えばこんな状況を考えます：
「旅行計画を立てたい．必ずきっちり2つの観光名所を見て回りたいが，その順番は気にしない．
計画の候補はどうなるだろう？」
つまり，
「『要素数2のset』のset」
がほしい，ということです．

ということで，setのsetを作ろうと試みます：

plan1 = {0,1}  # 観光名所0と観光名所1を順番を気にせず巡る計画
plan2 = {0,2}
plan3 = {2,0}
plans = {plan1, plan2, plan3}  # TypeError: unhashable type: 'set'

エラーで止まります．

setに格納するオブジェクトは，hash値を持つ（hash()が値を返す）必要があります．
これは効率的なsetを構築するための要求です．
他にも，演算子'='(__eq__()関数）を持つ必要もあります．
今回は，setがhash値を持たない，と怒られています．

よって，hash値が計算できる何かに変換してからsetに格納する必要があります．
setもlistもhashが計算できないのですが，tupleならば計算することができます．
そこで，tupleを使ってintの要素数2のsetを再現し，それを要素とすることにします：

class set_as_tuple:
    def __init__(self, e1, e2):
        if e1==e2:
            raise ValueError  # 同じ値は拒否
        if e1<e2:
            self.smaller = e1
            self.larger = e2
        else:
            self.smaller = e2
            self.larger = e1
    def __eq__(self, other):
        return self.smaller==other.smaller and self.larger==other.larger
    def __hash__(self):
        return hash((self.smaller, self.larger))
    def __str__(self):
        return '{'+str(self.smaller)+', '+str(self.larger)+'}'

plan1 = set_as_tuple(0,1)
plan2 = set_as_tuple(0,2)
plan3 = set_as_tuple(2,0)
plans = {plan1, plan2, plan3}
for e in plans:
    print(e)  # {0, 1} and {0, 2}