Pythonで〇×ゲームのAIを一から作成する　その52　set の性質と利用方法

# 目次と前回の記事

https://qiita.com/ysgeso/items/2381dd4e3283cbed49a0

https://qiita.com/ysgeso/items/58754ba98c286f414ea4

## これまでに作成したモジュール

以下のリンクから、これまでに作成したモジュールを見ることができます。

https://github.com/ysgeso/marubatsu/blob/master/052/marubatsu.py

https://github.com/ysgeso/marubatsu/blob/master/052/ai.py

## これまでに作成した AI

これまでに作成した AI の アルゴリズム は以下の通りです。

| ルール | アルゴリズム |
|:-:|:--|
| __[ルール1](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#%E6%9C%80%E5%88%9D%E3%81%AB%E8%A6%8B%E3%81%A4%E3%81%8B%E3%81%A3%E3%81%9F%E7%A9%BA%E3%81%84%E3%81%A6%E3%81%84%E3%82%8B%E3%83%9E%E3%82%B9%E3%81%AB%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai)__  | __左上から順__ に __空いているマス__ を探し、__最初に見つかったマス__ に __着手__ する |
| __[ルール2](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%81%AA%E3%83%9E%E3%82%B9%E3%81%AB%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai)__  | __ランダム__ なマスに __着手__ する |
| __[ルール3](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#%E3%83%AB%E3%83%BC%E3%83%AB-3-%E7%9C%9F%E3%82%93%E4%B8%AD%E3%81%AE%E3%83%9E%E3%82%B9%E3%81%AB%E5%84%AA%E5%85%88%E3%81%97%E3%81%A6%E7%9D%80%E6%89%8B%E3%81%99%E3%82%8B)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する | |
| __[ルール4](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#%E3%83%AB%E3%83%BC%E3%83%AB-4%E5%9B%9B%E9%9A%85%E3%81%AE%E3%83%9E%E3%82%B9%E3%81%AB%E5%84%AA%E5%85%88%E3%81%97%E3%81%A6%E7%9D%80%E6%89%8B%E3%81%99%E3%82%8B)__  | __真ん中__、__隅__ のマスの __順__ で __優先的__ に __着手__ する<br>既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する | あり |
| __[ルール5](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-5%E5%8B%9D%E3%81%A6%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AB%E5%8B%9D%E3%81%A4)__  | __勝てる場合__ に __勝つ__<br>そうでない場合は __ランダム__ なマスに __着手__ する | |
| __[ルール6](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-6%E7%9B%B8%E6%89%8B%E3%81%AE%E5%8B%9D%E5%88%A9%E3%82%92%E9%98%BB%E6%AD%A2%E3%81%99%E3%82%8B)__  | __勝てる場合__ に __勝つ__<br>そうでない場合は __相手の勝利__ を __阻止__ する<br>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール6改](https://qiita.com/ysgeso/items/6c0d73cc9ef4efd62d48#%E3%83%AB%E3%83%BC%E3%83%AB-6-%E6%94%B9%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __勝てる場合__ に __勝つ__<br>そうでない場合は __相手__ が __勝利できる__ 着手を __行わない__<br>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール7](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-7%E3%83%AB%E3%83%BC%E3%83%AB3-%E3%81%A8-%E3%83%AB%E3%83%BC%E3%83%AB-6-%E3%81%AE%E4%BD%B5%E7%94%A8)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>そうでない場合は __勝てる場合__ に __勝つ__<br>そうでない場合は __相手の勝利__ を __阻止__ する<br>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール7改](https://qiita.com/ysgeso/items/6c0d73cc9ef4efd62d48#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-%E3%83%AB%E3%83%BC%E3%83%AB-7-%E3%81%A7%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>そうでない場合は __勝てる場合__ に __勝つ__<br>そうでない場合は __相手__ が __勝利できる__ 着手を __行わない__<br>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール8](https://qiita.com/ysgeso/items/58754ba98c286f414ea4#%E3%83%AB%E3%83%BC%E3%83%AB-8-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>そうでない場合は __勝てる場合__ に __勝つ__<br>そうでない場合は __相手__ が __勝利できる__ 着手を __行わない__<br>そうでない場合は、__次__ の __自分の手番__ で __勝利できる__ ように、「__自 2 敵 0 空 1__」が 1 つ以上 __存在する__ 局面になる着手を行う<br>そうでない場合は __ランダム__ なマスに __着手__ する |

基準となる __`ai2`__ との __対戦結果__（単位は %）は以下の通りです。__太字__ は __`ai2 VS ai2` よりも__ __成績が良い__ 数値を表します。__欠陥__ の列は、__アルゴリズム__ に __欠陥__ があるため、__`ai2`__ との __対戦成績__ が __良くても強い__ とは __限らない__ ことを表します。欠陥の詳細については、関数名のリンク先の説明を見て下さい。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 | 欠陥 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|:-:|
| __[`ai1`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai1-%E3%81%AE%E5%AE%9A%E7%BE%A9)__<br>__[`ai1s`](https://qiita.com/ysgeso/items/3afe5630d7e615a28ebf#ai1s-%E3%81%AE%E4%BF%AE%E6%AD%A3)__  | __78.1__ | __17.5__ | 4.4 | __44.7__ | __51.6__ | 3.8 | __61.4__ | __34.5__ | 4.1 | あり |
| __[`ai2`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai2-%E3%81%AE%E5%AE%9A%E7%BE%A9)__<br>__[`ai2s`](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E9%96%A2%E6%95%B0%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E3%83%AB%E3%83%BC%E3%83%AB-2-%E3%81%A7%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | 58.7 | 28.8 | 12.6 | 29.1 | 58.6 | 12.3 | 43.9 | 43.7 | 12.5 | |
| __[`ai3`](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#ai3-%E3%81%AE%E5%AE%9F%E8%A3%85)__<br>__[`ai3s`](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E9%96%A2%E6%95%B0)__  | __69.3__ | __19.2__ | 11.5 | __38.9__ | __47.6__ | 13.5 | __54.1__ | __33.4__ | 12.5 | |
| __[`ai4`](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#%E3%83%AB%E3%83%BC%E3%83%AB-4%E5%9B%9B%E9%9A%85%E3%81%AE%E3%83%9E%E3%82%B9%E3%81%AB%E5%84%AA%E5%85%88%E3%81%97%E3%81%A6%E7%9D%80%E6%89%8B%E3%81%99%E3%82%8B)__<br>__[`ai4s`](https://qiita.com/ysgeso/items/3afe5630d7e615a28ebf#ai4s-%E3%81%AE%E4%BF%AE%E6%AD%A3%E3%81%A8%E5%8B%95%E4%BD%9C%E3%81%AE%E7%A2%BA%E8%AA%8D)__  | __83.0__ | __9.5__ | 7.4 | __57.2__ | __33.0__ | 9.7 | __70.1__ | __21.3__ | 8.6 | あり |
| __[`ai5`](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-5%E5%8B%9D%E3%81%A6%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AB%E5%8B%9D%E3%81%A4)__<br>__[`ai5s`](https://qiita.com/ysgeso/items/6c0d73cc9ef4efd62d48#ai5s-%E3%81%AE%E5%AE%9F%E8%A3%85)__  | __81.2__ | __12.3__ | 6.5 | __51.8__ | __39.8__ | 8.4 | __66.5__ | __26.0__ | 7.4 | |
| __[`ai6`](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-6%E7%9B%B8%E6%89%8B%E3%81%AE%E5%8B%9D%E5%88%A9%E3%82%92%E9%98%BB%E6%AD%A2%E3%81%99%E3%82%8B)__  | __88.9__ | __2.2__ | 8.9 | __70.3__ | __6.2__ | 23.5 | __79.6__ | __4.2__ | 16.2 |
| __[`ai6s`](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-6%E7%9B%B8%E6%89%8B%E3%81%AE%E5%8B%9D%E5%88%A9%E3%82%92%E9%98%BB%E6%AD%A2%E3%81%99%E3%82%8B)__  |   __88.6__ | __1.9__ | 9.5 | __69.4__ | __9.1__ | 21.5 | __79.0__ | __5.5__ | 15.5 |
| __[`ai7`](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-7%E3%83%AB%E3%83%BC%E3%83%AB3-%E3%81%A8-%E3%83%AB%E3%83%BC%E3%83%AB-6-%E3%81%AE%E4%BD%B5%E7%94%A8)__<br>__[`ai7s`](https://qiita.com/ysgeso/items/6c0d73cc9ef4efd62d48#ai7s-%E3%81%AE%E5%AE%9A%E7%BE%A9)__ | __95.8__ | __0.2__ | 4.0 | __82.3__ | __2.4__ | 15.3 | __89.0__ | __1.3__ | 9.7 |
| __[`ai8s`](https://qiita.com/ysgeso/items/58754ba98c286f414ea4#enum_markpats-%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-ai8s-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __98.2__ | __0.1__ | 1.6 | __89.4__ | __2.5__ | 8.1 | __93.8__ | __1.3__ | 4.9 |

# `enum_markpats` の問題点

[前回の記事](https://qiita.com/ysgeso/items/58754ba98c286f414ea4#%E3%83%9E%E3%83%BC%E3%82%AF%E3%81%AE%E6%95%B0%E3%81%AE%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3%E3%82%92%E5%88%97%E6%8C%99%E3%81%99%E3%82%8B%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9)で定義した __`enum_markpats`__ は、__[マークのパターン](https://qiita.com/ysgeso/items/58754ba98c286f414ea4#%E3%83%9E%E3%83%BC%E3%82%AF%E3%81%AE%E6%95%B0%E3%81%AE%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3%E3%82%92%E5%88%97%E6%8C%99%E3%81%99%E3%82%8B%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9) を列挙__ したデータを __list で表現__ しましたが、__list の要素__ には、__同じデータ__ が __複数存在できる__ ので、例えば下記のプログラムのように、__ゲーム開始時__ の局面に対して、__`enum_markpats`__ を呼び出して __表示__ すると、__同じ__ マークのパターンが __8 回も表示__ されてしまいます。

```python
from marubatsu import Marubatsu
from pprint import pprint

mb = Marubatsu()
pprint(mb.enum_markpats())
```

実行結果

```
[defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3})]
 ```

__プログラムが正しく動作する__ かどうかという __観点__ では、__list__ でも __全く問題__ はないのですが、__`enum_markpats`__ で __知りたい__ のは、__特定__ の __マークのパターン__ が __存在するか__ どうかなので、__同じ__ マークのパターンを表す __データ__ が、上記のように __8 つも存在__ するのは __無駄__ と言えるでしょう。この問題は、__set__ という __データ型__ を利用することで __解決__ できます。

__英単語__ としての __set__ は __集合__ を表し、__Python__ の __set__ は __文字通り__、__集合__ を __扱う__ ための __データ型__ です。__set__ は __list__ のように __頻繁に使われる__ わけでは __ありません__ が、__適切な場面__ で __利用__ することで、__集合の性質__ を持つ __データを扱う__ プログラムが __記述しやすく__ なったり、__処理__ の __効率を上げる__ ことができるので、今回の記事では、使い方を説明することにします。


# 集合とは何か

__set__ の説明を行う前に、__数学の用語__ としての __集合__ の __説明__ を行います。

__数学用語__ の __集合__ とは、__ものの集まり__ を表す __用語__ で、__集合__ の中に __含まれるもの__ のことを、__元__（げん） または __要素__（element）と呼びます。__本記事__ では __要素__ と __表記__ します。

__集合__ は、__現代数学__ における __最も基本__ となる __概念__ の一つです。このように説明すると、__難しそうだ__ と思う方が多いかもしれませんが、本記事では、それほど __難しい__ 集合の性質は __扱わない__ ので心配する必要はありません。

参考までに、wikipedia の集合の項目のリンクを下記に示します。

https://ja.wikipedia.org/wiki/%E9%9B%86%E5%90%88

## 有限集合と無限集合

集合には、__整数の集合__ のように、__無限個__ の __要素を持つ__ ものがあります。__無限個__ の要素を持つ集合を __無限集合__、数に限りがある __有限個__ の要素を持つ集合を __有限集合__ と呼びます。__Python__ の __set__ は __無限集合__ を __扱う__ ことは __できない__ と思います[^1]ので、本記事では、__有限集合のみ__ を __扱い__、以降は __集合__ と記述した場合は、__有限集合__ のことを __表す__ ことにします。

## 集合の性質

__集合__ は、主に下記のような __性質__ を持ちます。なお、__厳密__ な __集合の性質__ について知りたい方は、__数学__ を __学ぶ必要__ があります。

* __集合の中__ に __同じ要素__ は __重複__ して __存在しない__
* __集合の中__ の __要素__ に __順番__ は __存在しない__
* __要素__ が __存在しない__ 場合も、__集合__ と __みなされる__。そのような集合を、__空集合__ と呼ぶ
* __あるもの__ が集合の __要素__ に __含まれるか__ どうかを表す、__帰属関係__ を __考える__ ことができる
* __ある集合__ の __すべての要素__ が、__別の集合__ の __要素__ に __含まれるか__ どうかを表す、__包含関係__ を __考える__ ことができる
* __集合どうし__ に対する、__さまざまな演算__ を行うことができる。例えば、__集合 A__ と __集合 B__ に対して、__集合和__ という __演算__ を行うことで、__A と B__ の __要素を持つ__ 集合が __作成__ される

__`enum_markpats`__ が計算する、__マークのパターン__ を __列挙__ した __データ__ は、以下のように、__集合の性質__ を __満たす__ ので、そのデータを __集合とみなす__ ことができます。

* 同じ __マークのパターン__ が __重複する必要がない__
* __順番__ は __関係がない__
* __特定__ の __マークのパターン__ が __含まれるか__ という、__帰属関係__ を考えることができる

ピンとこない人がいるのではないかと思いますので、__上記__ の __集合の性質__ について、wikipedia の [リンク先](https://ja.wikipedia.org/wiki/%E9%9B%86%E5%90%88
)で紹介されている __トランプ__ を __具体例__ として説明します。

### 集合の例 

上記のリンク先で例として挙げられている __トランプ__ を使った __集合の例__ を紹介します。__集合__ は、一般的に __{ } の中__ に __要素__ を __,__ で __区切って表記__ するので、そのように表記します。

__トランプ__ の __マークの集合__ は { ♥, ♠, ♦, ♣ } の __4 つ__ の __要素__ を持つ集合です。

__トランプ__ の __数字の集合__ は { A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K } の __13 個__ の __要素__ を持つ集合です。なお、この集合の中には __A__、__J__、__Q__、__K__ という __文字__ が __含まれて__ いますが、__多くの場合__ では、それらは __1__、__11__、__12__、__13__ という __数字__ と __みなされる__ ので、本記事では __トランプ__ の __数字の集合__ を { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 } とします。

### 同じ要素が重複しない

__トランプ__ では、__それぞれのマーク__ を持つカードは __13 枚ずつ__ ありますが、__トランプ__ の __マーク__ の集合では、トランプの __カード__ から __マークだけ__ を __取り出した__、{ ♥, ♥, ♥, (♥ が 13 個並ぶ), ♠, ♠, ・・・以下略 } という、__マークを並べたもの__ を __集合__ と __考える__ ことは __ありません__。その __理由__ は、__集合__ が、__その中__ に __特定のものが存在するか__ どうかを __表す__ ことが __目的__ で __作られて__ おり、ものが __何個存在する__ かという __情報__ は __不要__ だからです。従って、__重複__ するものは __1 つ__ に __まとめられ__、__トランプ__ の __マーク__ の集合は、{ ♥, ♠, ♦, ♣ } となります。

### 集合の要素に順番はない

__集合__ の __要素の中__ に __特定の要素__ が存在するかどうかを表す際に、__要素__ の __順番__ の情報は __必要__ では __ありません__。例えば、__トランプ__ の __マーク__ を表す集合は、♥、♠、♦、♣ の __4 つの要素__ を __持つ__ という __性質のみ__ が __求められる__ ので、__マークの順番__ に __意味はありません__。

__集合__ を __表記__ する際には、__何らかの順番__ で要素を __記述する必要__ がありますが、その __順番__ に __意味はありません__。そのため、{ ♥, ♠, ♦, ♣ } と { ♦, ♣, ♥, ♠ } のように、__表記の順番__ が __異なっていても__、この 2 つは __同じ集合__ と __みなされます__。

__トランプ__ の __数字__ の集合のように、集合に含まれる __要素そのもの__ に __大きさなど__ の __順番が存在する__ 場合は、__一般的__ に { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 } のように、__分かりやすさ__ を __重視__ して __順番__ に並べて __表記__ しますが、この場合でも、集合の要素の __順番__ に __意味はありません__。従って、__トランプ__ の __数字__ の集合は、{ 2, 6, 13, 1, 11, 10, 12, 8, 9, 7, 4, 3, 5 } のように、__任意の順番__ で要素を __表記__ しても __かまいません__。

__複数のもの__ を __扱う際__ に、ものの __順番が重要__ な場合は、__集合__ を __利用__ することは __できない__ 点に __注意__ して下さい。__Python__ の場合は、set ではなく、__list を利用__ する __必要__ があります。

例えば、__トランプ__ の __マーク__ や __数字__ の __種類__ を扱いたい場合は、__集合__ を __利用__ することが __できます__ が、__トランプ__ の __カード__ を __シャッフルした後__ に __並べられた__ 52 枚のカードの __数字の内容__ を上から __順番__ に __扱いたい__ 場合は、「__重複した数字__ を __扱う必要__ がある」、「__順番__ が __必要__ である」という理由から、__集合__ として __扱う__ ことは __できません__。

### 空集合の例

例えば、__トランプ__ で「__20 以上__ の __数字__」の __集合__ は、そのようなトランプのカードが __存在しない__ ので __空集合__ になります。なお、__数学__ では __空集合__ には __{ }__ や __∅__ などの __複数の表記__ がありますが、__Python__ で __`{}`__ を記述すると、__空の dict__ を __表す__ 点に __注意が必要__ です。

### 帰属関係

__帰属関係__ とは、__あるもの__ が、__集合__ に __含まれている__ ことを表す __関係__ です。

__帰属関係__ が __あるか__ どうかを __調べる__ ことは、__無限集合__ の場合はそれほど __簡単な話ではありません__ が、__有限集合__ の場合は、__すべて__ の __集合の要素__ を __調べる__ ことで、要素の数が多い場合は時間がかかるかもしれませんが、__必ず判定__ することが __できます__。

例えば、__トランプ__ の __マーク__ の集合に、♠ が __含まれ__、■（四角の記号） が __含まれない__ ことは、__4 つ__ の要素を __調べる__ ことで __簡単に判定__ できます。

### 包含関係と相当関係

__包含関係__ は、__〇×ゲーム__ の __AI を作成__ する際に __利用しない__ ので、__難しいと思った方__ は簡単に __目を通しておくだけで良い__ と思います。後で __必要になった時__ に __読み返して__ 下さい。

__包含関係__ とは、__ある集合__ の __すべての要素__ が、__別の集合__ の __要素__ に __含まれる__（__帰属関係__ がある）という __関係__ を表します。例えば、__トランプ__ の __赤いマーク__ の集合である { ♥, ♦ } の __すべて__ の __要素__ は、__トランプ__ の __マーク__ の集合の { ♥, ♠, ♦, ♣ } の __要素__ に __含まれる__ ので、__包含関係__ があります。__包含関係__ には __方向__ があり、__集合 A__ の __すべての要素__ が __集合 B__ に __含まれる__ ことを、「__A は B に包含される__」または「__B は A を包含する__」のように __表記__ します。

__集合 A__ が __集合 B__ に __包含されるか__ どうかの __判定__ は、__A__ の __それぞれの要素__ が、__B__ に __帰属するか__ どうかを __判定__ し、__すべて__ の __A の要素__ が __B に帰属__ する場合に「__A は B に包含される__」 と __判定__ することが __できます__。従って、__有限集合__ の場合は、__2 つ__ の __集合__ の間に __包含関係__ が __あるか__ どうかを、__必ず判定__ することが __できます__。

__包含関係__ は __難しそう思える__ かもしれませんが、__図__ で示すとわかりやすいでしょう。__包含関係__ は、下図の __黄色の集合__ が、__緑の集合の中__ に __完全に含まれる__ という関係です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b2f4b6be-bf4c-7906-2a2e-54dc8b7eb9e6.png" width="250">

__2 つの集合__ の __要素__ が __完全に等しい__ ことを「2 つの集合が __相当関係__ である」、または 「2 つの集合が __等しい__」と呼びます。__A が B に包含される__ ことを、__数学__ では「$A ⊂ B$」と __表記__ します。また、__A と B__ が __相当である__（等しい）ことを「$A = B$」、A と B が __相当でない__（等しいくない）ことを「$A ≠ B$」と表記します。

__A と B が相当であるか__（$A = B$）の __判定__ は、__包含関係__ によって、「$A ⊂ B$ かつ $B ⊂ A$ である」場合に __相当__ であると __判定__ できます。証明は長くなるので省略しますが、それほど難しくはないので、興味がある方は調べてみて下さい。従って、__有限集合__ であれば、__必ず相当関係があるか__ どうかを __判定__ することが __できます__。

:::note
「__A が B に包含される__」（$A ⊂ B$）場合のことを「A は B の __部分集合__」であると表記します。また、「__A が B に包含される__」が「__A と B は相当でない__」場合（$A ⊂ B$ かつ $A ≠ B$）のことを「A は B の __真部分集合__」と表記します。
:::

:::note
「__A が B に包含される__」（$A ⊂ B$）が __満たされない__ 場合に、「__B が A に包含される__」（$A ⊃ B$）が __満たされるとは限らない__ 点に __注意__ して下さい。例えば、__トランプ__ の __偶数__ の集合 { 2, 4, 6, 8, 10, 12 } を __A__、__3 の倍数__ の集合 { 3, 6, 9, Q } を __B__ とした場合に、__集合 A__ は下図の __黄色__ の楕円、__集合 B__ は __緑色__ の楕円で __表されます__。図からわかるように、__A は B__ に __包含されません__ が、__B も A__ に __包含されません__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/55863b23-ec08-3b80-b2bf-dd75636cdef4.png" width="250">
:::

### 集合どうしの演算の例

__集合どうし__ の __演算__ も、〇×ゲームの AI では __利用しない__ ので、ここでは __集合和__ という演算 __のみを紹介__ します。他の演算については、この後で紹介します。

__トランプ__ で、__偶数の数字__ の集合 { 2, 4, 6, 8, 10, 12 } と __3 の倍数の数字__ の集合 { 3, 6, 9, Q } の __集合和__ は、それらの __両方__ の __要素__ を持つ { 2, 3, 4, 6, 8, 9, 10, 12 } になります。

__集合和__ は、下図の __黄色の集合__ と、__緑の集合__ の __両方の要素__ を __含む__ 集合になります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/55863b23-ec08-3b80-b2bf-dd75636cdef4.png" width="250">


# set の使い方

Python の __set__ は、上記のような __有限集合__ の __性質__ を持つデータを表現する __データ型__ です。

上記で説明した __集合の性質__ と __対応__ しながら、__set の使い方__ の __説明__ を行います。

set の詳細については、下記のリンク先を参照して下さい。

https://docs.python.org/ja/3/library/stdtypes.html#set-types-set-frozenset

## set の作成

__set__ は以下の __いずれかの方法__ で __作成__ することができます。

### set のリテラル

__set__ の __リテラル__ は __list__ と __似ています__ が、__外側__ を __囲う記号__ が __`[`__ と __`]`__ ではなく、__`{`__ と __`}`__ である点が __異なります__。なお、__`{`__ と __`}`__ で __囲んで記述__ する点は __dict__ のリテラルと __同じ__ ですが、__`キー:キーの値`__ __ではなく__、__set の要素__ となるデータ __だけを記述__ する点が __異なります__。

下記は、__トランプ__ の __マーク__ を要素とする __set__ を __`print` で表示__ するプログラムです。__`print` で表示__ した場合は、__set のリテラル__ と __同じ内容__ が __表示__ されます。

```python
print({"♠", "♥", "♦", "♣"})
```

実行結果

```
{'♠', '♥', '♦', '♣'}
```

__set__ は、__集合__ と __同様__ に、__同じ要素__ が __重複しない__ という __性質を持つ__ ので、下記のプログラムのように、__set__ の __リテラル__ に、__同じデータ__ を __複数記述__ した場合は、__同じデータ__ が __1 つにまとめられた set__ が __作成__ されます。

```python
print({"♠", "♠", "♠", "♥", "♥", "♥", "♦", "♦", "♦", "♣", "♣", "♣"})
```


実行結果

```
{'♠', '♥', '♦', '♣'}
```

### 空の set のリテラル

__空集合__ を表す、__要素__ が __存在しない set__ のことを、__空の set__ と呼びます。__空の set__ の __リテラルだけ__ は、`{}` __ではなく__、__`set()`__ のように __記述__ する __必要がある__ 点に __注意__ して下さい。その __理由__ は、__`{}`__ のように __記述__ すると、__空の dict__ と __みなされる__ からです。__空の set__ を __`print` で表示__ すると、下記のプログラムの __1 行目__ のように __set() が表示__ されます。

```python
print(set())  # 空の set のみ、必ずこのように記述する必要がある
print({})     # こちらは空の dict を表す
```

実行結果
```
set()
{}
```

### list からの作成

上記で利用した、__`set`__ は、__データ型__ を表す __[組み込み型のクラス](https://qiita.com/ysgeso/items/a189461ae32a6531ff7f#%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E5%9E%8B%E3%81%AE%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%A8%E3%82%A4%E3%83%B3%E3%82%B9%E3%82%BF%E3%83%B3%E3%82%B9)__ です。下記のプログラムのように、__`set`__ の __引数__ に __list を記述__ することで、記述した __list と同じ要素__ を持つ __set__ の __インスタンス__ を __作成__ することができます。__2 行目__ のように、__同じ要素__ を __複数持つ list__ を __記述__ した場合は、__先程と同様__ に、__同じデータ__ が __1 つ__ に __まとめられた set__  が __作成__ されます。


```python
print(set(["♠", "♥", "♦", "♣"]))
print(set(["♠", "♠", "♠", "♥", "♥", "♥", "♦", "♦", "♦", "♣", "♣", "♣"]))
```

実行結果

```
{'♦', '♥', '♣', '♠'}
{'♦', '♥', '♣', '♠'}
```

なお、下記のプログラムのように、組み込み型のクラスである __`list`__ の __実引数__ に __set を記述__ することで、__set__ を __list に変換__ することも __できます__。そのことは、__実行結果__ の __外側の記号__ が、__list__ を表す __`[`__ と __`]`__ であることから __確認__ できます。

```python
print(list({"♠", "♥", "♦", "♣"}))
```

実行結果

```
['♠', '♥', '♦', '♣']
```

### set 内包表記

__[list 内包表記](https://qiita.com/ysgeso/items/2a436b3819bef9a6a2b4#%E3%83%AA%E3%82%B9%E3%83%88%E5%86%85%E5%8C%85%E8%A1%A8%E8%A8%98)__ と __同様__ の __set 内包表記__ で、下記のプログラムのように __set を作成__ することが __できます__。__list 内包表記__ との __違い__ は、__外側の記号__ が __`{`__ と __`}`__ である点 __だけ__ です。

```python
print({ i for i in range(10) })
```

実行結果

```
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
```

### set が扱えるデータ

__list__ は、__任意__ の __オブジェクト__ を __要素__ にできましたが、__set__ は [以前の記事](https://qiita.com/ysgeso/items/3afe5630d7e615a28ebf#%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E5%8F%AF%E8%83%BD%E3%81%AA%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%81%A8%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E5%80%A4)で説明した __ハッシュ可能__ なオブジェクト __のみ__ を __要素__ に __できます__。

__list__ のような、ハッシュ可能 __でない__  オブジェクトを __set の要素__ にしようとすると、下記のプログラムのように __エラーが発生__ します。なお、set がハッシュ可能なオブジェクトしか扱えない理由については後で説明します。

```python
print({1, []})
```

実行結果

```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[8], line 1
----> 1 print({1, []})

TypeError: unhashable type: 'list'
```

:::note
上記のエラーメッセージは、以下のような意味を持ちます。

* __TypeError__
データ型（type）に関するエラー
* __unhashable type: 'list'__
list はハッシュ可能（hashable）なデータ型（type）ではない（un）
:::

## 帰属関係の判定

__あるデータ__ が、__set__  の __要素__ に __含まれるか__ どうかという __帰属判定__ は、下記のプログラムのように、__list と同様__ の方法で、__`in` 演算子__ を使って __判定できます__。

```python
marks = {"♠", "♥", "♦", "♣"}
print("♠" in marks)  # ♠ は marks に含まれる
print("■" in marks)  # ■（四角）は marks に含まれない
```

実行結果
```
True
False
```

__set__ に __含まれない__ かどうかの __判定__ も、__list と同様__ に __not in 演算子__ を利用できます。

```python
marks = {"♠", "♥", "♦", "♣"}
print("♠" not in marks)
print("■" not in marks)
```

実行結果
```
False
True
```

## 包含関係と相当関係（等しい）の判定

下記の表の __比較演算子__ によって、__set どうし__ の __包含関係__ や __相当関係__ を __判定__ することができます。下記の「__`True` になる条件__」の __列__ は、__演算子の左右__ に __A__ と __B__ という __2 つ__ の __set__ を記述して __比較__ した場合の __説明__ です。また、参考までに __数学の用語__ を表に示します。

| 演算子 | `True` になる条件 | 数学の記法と用語 |
|:-:|:--|:--|
| __`==`__  |  A と B が等しい（同じ要素を持つ） | $A = B$<br>A と B は相当（等しい） |
| __`!=`__  |  A と B が等しくない（異なる要素がある） | $A ≠ B$ |
| __`>`__ | B のすべての要素を A が含む<br>ただし、A と B が等しい場合を除く  | $A ⊃ B$ かつ $A ≠ B$<br>B は A の真部分集合  |
| __`>=`__ | B のすべての要素を A が含む<br>A と B が等しくても良い  | $A ⊃ B$<br>B は A の部分集合 | 
| __`<`__ | A のすべての要素を B が含む<br>ただし、A と B が等しい場合を除く  | $A ⊂ B$ かつ $A ≠ B$<br>A は B の真部分集合 |
| __`<=`__ | A のすべての要素を B が含む<br>A と B が等しくても良い  | $A ⊂ B$<br>A は B の部分集合 |

:::note
__set__ には、__上記の演算子__ と __同じ処理__ を行う __メソッド__ が用意されています。また、__上記__ では __行えない__ 、__A__ と __B__ が __共通の要素を持たない__ ことを __判定__ する __`isdisjoint`__ というメソッドがあります。興味がある方は、[このリンク先](
https://docs.python.org/ja/3/library/stdtypes.html#set-types-set-frozenset)を参照して下さい。
:::

### 比較演算子の利用例

下記のプログラムは、__上記の演算子__ の __利用例__ です。__A__ と __B__ は、__set__ の __リテラル__ を記述する際に、__異なる順番__ で __4 つのマーク__ を __記述__ していますが、先ほど説明したように、__集合の要素__ に __順番はない__ ので、__A__ と __B__ は __同一__ の __set__ と __みなされます__。__その他__ については、一つ一つを説明すると長くなりすぎるので説明は __省略__ します。__上記の表__ と、下記のプログラムの __実行結果__ を各自で __見比べて下さい__。

```python
A = {"♠", "♥", "♦", "♣"}
B = {"♦", "♥", "♠", "♣"}
C = {"♥", "♦"}            # 赤いマークのみの集合
D = {"♠", "♥", "■"}       # トランプのマークと関係ない ■ が混じっている

print("A == B", A == B)
print("A == C", A == C)
print("A == D", A == D)
print()

print("A != B", A != B)
print("A != C", A != C)
print("A != D", A != D)
print()

print("A > B", A > B)
print("A > C", A > C)
print("A > D", A > D)
print()

print("A >= B", A >= B)
print("A >= C", A >= C)
print("A >= D", A >= D)
print()

print("B < A", B < A)
print("C < A", C < A)
print("D < A", D < A)
print()

print("B <= A", B <= A)
print("C <= A", C <= A)
print("D <= A", D <= A)
```

実行結果

```
A == B True
A == C False
A == D False

A != B False
A != C True
A != D True

A > B False
A > C True
A > D False

A >= B True
A >= C True
A >= D False

B < A False
C < A True
D < A False

B <= A True
C <= A True
D <= A False
```

:::note
__list__ に対して __`==` 演算子__ で __比較__ した場合は、下記のプログラムのように、__要素の順番__ も __含めて同じ__ でなければ __`True`__ と __みなされません__。__その点に注意__ して下さい。


```python
A = ["♠", "♥", "♦", "♣"]
B = ["♦", "♥", "♠", "♣"]

print(A == B)
```

実行結果

```
False
```
:::

## set どうしの演算

__下記__ の表の __演算子__ によって、__set どうし__ の __演算__ を行い、__新しい set__ を __作成__ することができます。下記の説明では、__A__ と __B__ という __2 つの集合__ を __演算子で演算__ した場合の説明です。

| 演算子 | 関係 |
|:-:|:--|
| <code>\|</code>  |  A と B の __両方の要素__ を持つ、__和集合__ を計算する |
| __`&`__  |  A と B の __共通する要素__ を持つ、__積集合__ を計算する |
| __`-`__ | __A の要素から__、__B の要素__ を __削除__ した、__差集合__ を計算する<br>__B にのみ__ 存在する要素は __差集合__ には __含まれない__  |
| __`^`__ | __A__ と __B__ の __いずれかのみ__ に含まれる、__対象差__ を計算する  |

下記のプログラムは、__上記の演算子__ の __利用例__ です。実行結果からわかるように、__一部の演算__ では、__`print` で表示__ される __要素の順番__ が __変化__ しますが、先ほど説明したように __set__ の __要素の順番__ に __意味はない__ ので、__表示の順番__ が __変わっても問題はありません__。

```python
A = {2, 4, 6, 8, 10, 12}  # トランプの偶数の数字
B = {3, 6, 9, 12}         # トランプの 3 の倍数の数字

print("A | B", A | B)
print("A & B", A & B)
print("A - B", A - B)
print("A ^ B", A ^ B)
```

実行結果

```
A | B {2, 3, 4, 6, 8, 9, 10, 12}
A & B {12, 6}
A - B {8, 2, 10, 4}
A ^ B {2, 3, 4, 8, 9, 10}
```

上記のうち、__和集合__ を計算する __演算子__ は、__数値__ の __和を計算__ する際に利用する __`+` ではない__ 点に __注意が必要__ です。実際に __set__ に対して __`+` 演算子__ で __計算__ を行おうとすると、下記のプログラムのように、__エラーが発生__ します。

```python
print({1, 2} + {3})
```

実行結果

```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[14], line 1
----> 1 print({1, 2} + {3})

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

:::note
上記のエラーメッセージは、以下のような意味を持ちます。

* __TypeError__
データ型（type）に関するエラー
* __unsupported operand type(s) for +: 'set' and 'set'__
\+ 演算子は set と（and）set 型（types）の値（operand[^2]）の演算をサポートしていない（unsupported）
:::

__set__ の __和集合__ の計算に __`+`__ が __使われない理由__ の一つは、__set__  に対する __和集合__ の計算では、__重複する要素__ が __1 つ__ に __まとめられる__ からです。それに対して、__list の結合__ を行う __`+` 演算子__ では、下記のプログラムのように、__重複する要素__ が __まとめられる__ ことは __ありません__。

```python
print([1, 2, 3] + [1, 2])
```

実行結果

```
[1, 2, 3, 1, 2]
```

:::note
__他の理由__ としては、__和集合の計算__ が、まだ説明していない、__<code>\|</code>__ 演算子を使う、__ビット演算__ の __論理和の計算__ に __似ている__ という理由があると思います。
:::

## set に対するさまざまな操作

__set__ に対して行うことができる、__さまざまな操作__ について説明します。

### `add` メソッドによる要素の追加

__set__ に対して __要素を追加__ する場合は、下記のプログラムのように、__`add` メソッド__ を利用します。__list__ に要素を追加する __`append` メソッド__ とは __名前が異なる__ 点に __注意__ して下さい。

```python
a = { 1, 2 }
a.add(3)          # append ではない点に注意
print(a)
```

実行結果
```
{1, 2, 3}
```

また、[以前の記事](https://qiita.com/ysgeso/items/59e51d983a32ac4bc5db#-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AB%E3%82%88%E3%82%8B-list-%E3%81%AE%E7%B5%90%E5%90%88)のノートで紹介した、__list__ の __要素の追加__ を行う際に利用できた __`+=` 演算子__ は、__set__  に対して行うと、下記のプログラムのように __エラーが発生__ する点にも __注意が必要__ です。__同様の処理__ は、次に説明する __`|=` 演算子__ で行うことができます。

```python
a += {4, 5}
```

実行結果

```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[32], line 1
----> 1 a += {4, 5}

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

:::note
上記のエラーメッセージは、以下のような意味を持ちます。

* __TypeError__
データ型（type）に関するエラー
* __unsupported operand type(s) for +: 'set' and 'set'__
+= 演算子は set と（and）set 型（types）の値（operand[^2]）の演算をサポートしていない（unsupported）
:::

### `|=` 演算子による要素の追加

__`|=`__ 演算子を使って、__set__ に __別の set__ の __要素__ を __すべて追加__ することができます。下記のプログラムの __`3`__ のように、__重複する要素__ がある場合は、__一つ__ に __まとめられます__。

```python
a = {1, 2, 3}
a |= {3, 4, 5}
print(a)
```

実行結果

```
{1, 2, 3, 4, 5}
```

#### `|=` 演算子に関する注意点

__`|=`__ 演算子は、__見た目上__ は、__前後の set__ に対して __`|` 演算子__ によって __和集合__ を __計算__ し、__`|=` の前__ に __記述された変数__ に __代入__ するという処理を行うように __見えるかもしれません__。

例えば、下記のプログラムの __1 行目__ と、__2 行目__ は __同じ処理__ を行うように __見えるかもしれません__ が、__実際__ には __異なる処理__ を __行う__ 点に __注意が必要__ です。


```python
a |= {3, 4, 5}
a = a | {3, 4, 5}
```

上記の __1 行目__ では、__`a`__ に __代入__ された __set__ に `+=` の __右の set__ の __要素が追加__ されます。一方 __2 行目__ では、__`a | {3, 4, 5}`__ の __計算結果__ を表す __新しい set__ が __作成__ され、その __新しい set__ で __`a`__ が __参照__ する __オブジェクトを更新__ する点が異なります。

* __`|=`__ 演算子では、__`|=`__ の __前に記述__ された __変数__ が __参照__ するオブジェクトは __変化しない__
* __`=`__ 演算子では、__`=`__ の __前に記述__ された __変数__ が __参照__ するオブジェクトは __変化する__

そのことは、下記のプログラムのように、__変数__ が __参照__ する __オブジェクトの id__ を __表示__ することで __確認__ できます。__この違い__ を __理解していない__ と __バグが発生__ する __可能性__ があります。具体例については、そのような状況が実際に起きる場合に紹介する予定です。

```python
a = {1, 2, 3}
print(id(a))     
a |= {3, 4, 5}     # こちらは、a に要素を追加する処理
print(id(a))       # 2 行前と同じ id が表示される

a = {1, 2, 3}
print(id(a))
a = a | {3, 4, 5}  # こちらは、新しい set を作成し、a に代入する処理
print(id(a))       # 2 行前と異なる id が表示される
```

実行結果
```
1661492119360
1661492119360
1661492117568
1661492120704
```

なお、__この性質__ は、__list__ に対する __`+=` 演算子__ や、__次__ で説明する __演算子__ にも __共通__ します。

### set の内容を更新する他の演算子

先程紹介した、__`&`__、__`-`__、__`^`__ に対応する __`&=`__、__`-=`__、__`^=`__ 演算子があります。いずれも、__演算子の前__ に記述された __変数__ に代入されたの __set の内容__ を、__対応する演算子__ による __演算の結果__ で __更新__ する処理を行い、__`|=` と同様__ に、__変数__ が __参照__ する __オブジェクト__ は __変化しません__。

下記のプログラムは、それらの演算子の __使用例__ です。これらの __演算子__ による __演算によって__、__`a` の値__ が __更新される__ ので、__次の演算__ を __行う前__ に __`a`__ に __元の値__ を __代入しなおし__ ています。なお、__`b`__ の __値__ は __変化しない__ ので __代入し直す必要__ は __ありません__。

```python
a = {2, 4, 6, 8, 10, 12}
b = {3, 6, 9, 12}

a &= b
print(a)

a = {2, 4, 6, 8, 10, 12}
a -= b
print(a)

a = {2, 4, 6, 8, 10, 12}
a ^= b
print(a)
```

実行結果

```
{12, 6}
{2, 4, 8, 10}
{2, 3, 4, 8, 9, 10}
```

### 要素の削除

下記の表は、__set__ の __要素を削除__ する方法です。__`pop` 以外__ の __メソッド__ は __値を返しません__。

| 方法 | 意味 |
|:--|:--|
| __`remove` メソッド__  | __実引数__ に記述したものと __同じ要素__ を __削除__ する<br>__記述__ した __要素が存在しない__ 場合は、__エラーが発生__ する  |
| __`discard` メソッド__  | __実引数__ に記述したものと __同じ要素__ を __削除__ する<br>__記述__ した __要素が存在しない__ 場合は、__何も行わない__  |
| __`pop` メソッド__  | __いずれか 1 つ__ の要素を __削除__ し、__削除した値__ を __返す__<br>なお、__削除する要素__ は __指定できない__ |
| __`clear` メソッド__  |  __すべての要素__ を __削除__ し、__空の set にする__ |
| __`-=` 演算子__  | __演算子の右__ に __記述__ した __set の要素__ を __すべて削除__ する  |

下記のプログラムは、それぞれの __利用例__ です。__`-=` 演算子__ は __先程説明した__ ので __省略__ します。なお、__`pop` メソッド__ は、個人的にはあまり __使い道がない__ のではないかと思います。

```python
a = {1, 2, 3, 4, 5}

a.remove(5)   # 5 を削除する
print(a)

a.discard(4)  # 4 を削除する
print(a)

a.discard(6)  # 存在しない 6 を discard で指定した場合は何も起こらない
print(a)

print(a.pop()) # いずれか 1 つの要素を削除し、その値を返す
print(a)       # 上の行で表示された値の要素が削除されている

a.clear()      # すべての要素を削除する
print(a)       # 空の set を表す set() が表示される
```

実行結果
```
{1, 2, 3, 4}
{1, 2, 3}
{1, 2, 3}
1
{2, 3}
set()
```

下記のプログラムは、__`remove` メソッド__ で、__存在しない要素__ を __削除__ しようとする例で、実行結果からわかるように、__エラーが発生__ します。

```python
a = {1, 2, 3}
a.remove(5)
```

実行結果

```
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[19], line 2
      1 a = {1, 2, 3}
----> 2 a.remove(5)

KeyError: 5
```

:::note
上記のエラーメッセージは、以下のような意味を持ちます。

* __KeyError__
キー（key）に関するエラー
* __5__
5 というキーは存在しない
:::

### 要素の数の計算

__set__ の __要素の数__ は、__list と同様__ に、組み込み関数 __`len`__ を使って下記のプログラムのように __計算できます__。

```python
print(len({1, 2, 3}))
print(len(set()))      # 空の set の場合の要素の数は 0
```

実行結果

```
3
0
```

### for 文による要素の列挙

__set__ は __反復可能オブジェクト__ なので、__for 文__ の __反復可能オブジェクト__ に __記述__ することで、下記のプログラムのように、__list と同様__ に __要素__ を __順番に取り出す__ ことができます。

なお、__set__ の __要素__ は、__set__ に __挿入した順番__ で __取り出され__ ますが、__`&=`__ 演算子などによって __set__ の __要素を更新__ した場合などで、__順番が変更される__ 場合があります。ただし、__set__ の __要素の順番__ に __意味はない__ ので、__表示される順番__ は __重要ではありません__。

```python
print("list")
for i in [1, 2, 3]:
    print(i)
print("set")
for i in (1, 2, 3):
    print(i)
```    

実行結果
```
list
1
2
3
set
1
2
3
```

### インデックスは利用できない

__set__ は、__要素の順番__ に __意味はない__ ので、__list__ のように、__インデックス__ を使って __特定の順番の要素__ を __取りだしたり__、__値を変更__ することは __できません__。下記のプログラムのように __set__ に __インデックスを記述__ して __要素を参照__ しようとすると、__エラーが発生__ します。

```python
a = {1, 2, 3}
print(a[1])
```

実行結果

```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[22], line 2
      1 a = {1, 2, 3}
----> 2 print(a[1])

TypeError: 'set' object is not subscriptable
```

:::note
上記のエラーメッセージは、以下のような意味を持ちます。

* __TypeError__
データ型（Type）に関するエラー
* __`set` object is not subscriptable__
set は、`[]` を使ってその中のデータを参照する（subscript）ことはできない（is not able）
:::

## set と list の使い分け

ここまでの説明で __set__ と __list__ は __似ている部分が多い__ と思った方が多いのではないかと思います。__実際__ に __set__ と __list__ は、__多くの点__ で __似ていますが__、__下記__ の点が __大きく異なる__ ので、__状況に応じて__ 適切に __使い分ける必要__ があります。

* set は、その __要素の中__ に、__同じデータ__ を __複数持つ__ ことが __できない__
* set の __要素の順番__ は __意味を持たない__
* set の __要素__ を、__インデックス__ を指定して __参照__ することは __できない__。できるのは、__特定の値__ が __set__ の __要素の中__ に __存在するか__ どうかを __判定する__（帰属判定）こと __だけ__ である
* set は、__要素__ の __追加と削除__ を行うことはできるが、__要素の値__ を __直接変更できない__
* set は、__ハッシュ可能__ なオブジェクト __しか扱えない__

上記の性質のうち、__最後の性質以外__ は、数学の __集合の性質__ です。従って、__set__ は、__複数のデータ__ を __集合として扱いたい__ 場合に __利用__ します。具体的には、主に、__下記__ の __1 ～ 3__ の __性質を持つ__ データを __扱う際__ に __利用__ します。

1. 下記の __いずれか__（または複数）の __目的__ で __複数のデータ__ を __扱いたい__
    1. __複数のデータ__ の中に、__特定のデータ__ が __存在するか__（__帰属関係__） を __判定したい__
    2. __複数のデータどうし__ が、__包含関係__ や __相当関係__ にあるかを __判定したい__
    3. __複数のデータどうし__ の、__和集合など__ の __集合としての演算__ を __行いたい__
2. __複数のデータ__ の __順番__ と __個数__ を __扱う必要がない__
3. __複数のデータ__ の __内容__ を後から __変更しない__

__`enum_markpats`__ が __計算__ する、__マークのパターン__ の __一覧__ は、上記の __1-1、2、3__ の __性質を満たす__ データなので、__set__ を使って __表現__ することが __できます__。

:::note
上記の __3 の性質__ の __意味__ が __分かりづらい__ と思いますので補足します。

例えば、__`enum_markpats`__ によって、__マークのパターン__ の __一覧__ として「自 1 敵 0 空 2」と「自 0 敵 0 空 3」いう __2 つ__ の __マークパターン__ が __計算__ された場合のことを考えてみて下さい。__局面__ が __変わらなければ__、その局面の __マークのパターン__ の __一覧__ は __変わりません__。従って、__局面__ が __変わらない限り__、__マークのパターン__ の __一覧__ の __いずれか__ を例えば「自 1 敵 1 空 1」のように __変更__ しては __いけない__ ことがわかります。これが、「__内容__ を __後から変更しない__」ということの意味です。
:::

従って、逆に __下記__ の __いずれか__ の __性質を__ 持つ __データ__ を扱いたい場合は、__set__ ではなく、__list__、__tuple__、__dict__ などを利用する __必要__ があります。ただし、__3 つ目の性質__ が __必要な場合__ は __tuple__ は __利用できません__。

1. __複数のデータ__ を、__順番を付けて__ 管理したい
2. __同じデータ__ を __複数個__ 管理したい
3. __管理するデータ__ の __内容__ を __後から変更__ したい

## set がハッシュ可能なオブジェクトしか扱えない理由

__set__ の __性質__ の中で、__ハッシュ可能__ なオブジェクト __しか扱えない__ という __性質__ が、__集合__ の __性質__ とは __関係ない__ ように __見える__ かもしれませんので、__この性質__ がある __理由__ を説明します。

### 処理を高速に行うため

__set__ に対して __行うことができる__、下記のような __set に対して__ 行うことができる __さまざまな演算__ では、__特定のデータ__ と __set の要素__ が __等しいか__ どうかを __判定する必要__ があります。また、__ハッシュ可能なオブジェクト__ は、__ハッシュ値__ を __利用__ することで、__等しいかどうか__ を、__高速に判定__ できます。そのため、__set__ の __要素__ を __ハッシュ可能なオブジェクト__ に __限定する__ ことで、__set__ に関する __多くの処理__ を __高速に行う__ ことが __できるようになります__。

* __`in`__ 演算による __帰属関係__ の __判定__
* __比較演算子__ による __包含関係__、__相当関係__ の __判定__
* __和集合など__ の __set どうし__ の __さまざまな演算__

そのことを __確認__ するために、__set__ と __list__ の両方で __共通__ して __行う__ ことが __できる__、__`in` 演算子__ による __帰属関係__ の __判定__ の __処理速度__ を、__set__ と __list__ で __比較__ することにします。

なお、__下記の比較__ は、__ざっくりとした比較__ なので、__厳密__ な set と list の __処理速度の比較__ には __なっていません__ が、__処理速度__ の __圧倒的な差__ から、__要素が多い場合__ は、__set__ のほうが __list より__ も __高速__ に __処理を行う__ ことが __できる__ という __事実__ は間違いなく __確認できます__。

下記のプログラムは、__0 ~ 100000 未満__ の、__10 万個__ の __整数__ を __要素__ として持つ __list__ と __set__ を __内包表現__ を使って __作成__ し、__`l`__ と __`s`__ という名前の変数に代入しています。

```python
l = [ i for i in range(100000) ] # 10 万個の要素を持つ list
s = { i for i in range(100000) } # 10 万個の要素を持つ set
```

次に、下記のプログラムで、__0 ~ 100000 未満__ の __10 万個__ の __整数__ が __`l`__ の要素に __含まれるか__ どうかを __in 演算子__ で __判定__ し、__その数を数える__ という処理を行います。__10 万個__ の __すべて__ の __整数__ が __`l` に含まれる__ ので __実行結果__ には __10万__ が __表示__ されます。__筆者のパソコン__ で、下記のプログラムを実行すると __約 54.6 秒__ かかりました。つまり、__一回__ の __`in` 演算子__ の判定で、__平均__ するとその __10 万分の 1__  の、__約 0.546 ミリ秒__ の __処理時間__ がかかります。

```python
count = 0
for i in range(100000):
    if i in s:
        count += 1
print(count)
```

実行結果

```
100000
```

次に、下記のプログラムで __set__ が __代入__ された __`s`__ に対して __同じ処理__ を行います。__筆者のパソコン__ で、下記のプログラムを実行すると、__一瞬__ で __処理が終__ 了し、__JupyterLab__ の __セル__ には __0.0 秒__ と __表示__ されました。

```python
count = 0
for i in range(100000):
    if i in s:
        count += 1
print(count)
```

実行結果

```
100000
```

__あまりに速く__ 計算が行われてしまったため、__JupyterLab__ の __セルの表示__ では __処理時間__ をうまく __計測できなかった__ ので、__in 演算子__ で __処理__ を行う __回数__ を下記のプログラムのように、__100 倍__ の __1000 万回__ 行うことにします。なお、__`s`__ の要素には、__10 万まで__ の __整数__ しか __存在しない__ ので、下記のプログラムの __3 行目__ のように、__余りを計算__ する __`%` 演算子__ を使って __`i`__ を __10 万で割った余り__ が __`s`__ の要素に __存在するか__ どうかを __計算する__ ことで、__常に__ `s` に __要素が存在__ する __値__ で __in 演算子__ の __計算を行う__ ようにしています。

__筆者のパソコン__ で、下記のプログラムを実行すると __約 1.8 秒__ の時間がかかりました。つまり、__一回__ の __`in` 演算子__ の判定で、__平均__ するとその __100 万分の 1__  の、__約 0.0018 ミリ秒__ の __処理時間__ がかかります。

```python
count = 0
for i in range(10000000):
    if i % 100000 in s:
        count += 1
print(count)
```

実行結果

```
10000000
```

__筆者のパソコン__ では、__1 回あたり__ の __in 演算子__ の __処理速度__ は、__list__ の場合は __約 0.546 ミリ秒__、__set__ の場合は、__約 0.0018 秒__ かかったので、__set__ のほうが __0.546 ÷ 0.0018 = 約 300 倍__ の __速度__ で __処理を行う__ ことができることが分かりました。

このように、__ハッシュ可能なオブジェクト__ に __要素の値__ を __限定__ することで、__同じ in 演算子__ による __処理__ を行った場合でも、__list__ と __set__ では __処理時間__ に __大きな差__ が __生じます__。

#### 要素の数と処理速度の差の関係

なお、詳しい説明は省略しますが、__in 演算子__ による __処理速度__ は、__list の場合__ は、__list__ の __要素の数__ に __ほぼ比例__ しますが、__set の場合__ は __ほとんど変わりません__。例えば、__要素の数__ を下記のプログラムのように、__1/10__ の __1 万__ に __減らして__ 先程と __同様の処理__ を行ってみます。

```python
l = [ i for i in range(10000) ] # 1 万個の要素を持つ list
s = { i for i in range(10000) } # 1 万個の要素を持つ set
```

下記のプログラム（__3 行目__ を __`i % 10000`__ に __修正__ しています）を実行すると、__筆者のパソコン__ では、__先程__ の __約 1/10__ の __約 5.6 秒__ の __処理時間__ がかかりました。

```python
count = 0
for i in range(100000):
    if i % 10000 in l:
        count += 1
print(count)
```

一方、下記のプログラムを実行すると、__筆者のパソコン__ では __約 1.8 秒__ かかり、__処理時間__ が __変わらない__ 事が分かります。なお、__処理時間__ の __計測__ は、__パソコンの状態__ によって __全く同じ計算__ を行った場合でも __若干の変化__ があります。この例では __処理時間__ は __変わりません__ でしたが、__理論的__ には __set の要素の数__ が __少なくなる__ と __処理時間__ も __若干短く__ なります。

:::note
__より厳密__ な __処理時間__ の __計測方法__ については、__今後の記事__ で __紹介__ します。
:::

```python
count = 0
for i in range(10000000):
    if i % 10000 in s:
        count += 1
print(count)
```

このように、__set__ と __list__ の __処理速度__ は、__要素の数__ が __大きい程__、顕著な __差が生じます__ が、__要素の数__ が __10 程度__ であれば、__処理速度__ の __差__ は __ほとんどありません__。実際に、下記のプログラムで、__要素の数__ が __10__ の __list__ と __set__ で __1000 万回__ の __in 演算子__ の __処理時間__ を __計測__ した所、__list__ が __約 2.1 秒__、__set__ が __約 1.4 秒__ となり、__処理時間__ は __あまり変わりません__ でした。

:::note
先程言及したように、__要素の数__ が __1 万より__ 大きく __少ない 10__ の場合は、__set__ の __処理時間__ が、__先程__ の __約 1.8 秒より__ も __若干短く__ なっています。
:::

なお、__それぞれ__ の __処理時間__ を __JupyterLab__ の __セルの表示__ で __計測__ するためには、下記の __3 つ__ のプログラムを __別々のセル__ で __実行する必要__ がある点に __注意__ して下さい。

```python
l = [ i for i in range(10) ] # 10 個の要素を持つ list
s = { i for i in range(10) } # 10 個の要素を持つ set
```

```python
count = 0
for i in range(10000000):
    if i % 10 in l:
        count += 1
print(count)
```

```python
count = 0
for i in range(10000000):
    if i % 10 in s:
        count += 1
print(count)
```

このことから、__in 演算子__ を使って __帰属判定__ を行う際に、__set__ と __list__ の __どちら__ を使っても __良い場合__ では、__要素の数__ が __数十__ を __超える__ ことが __判明__ した時点で、__set__ を __積極的に利用__ したほうが __良い__ ことが分かります。

残念ながら、__〇×ゲーム__ の __マークのパターン__ の場合は、__最大__ でも __要素の数__ が __8 しかない__ ので、__処理速度__ の面では __set__ と __list__ で __大きな差はない__ でしょう。そのことは、__set を利用__ するプログラムで __`ai8s`__ を __修正後__ に __検証__ することにします。

### set の性質を満たすため

__set の性質__ に、__要素の値__ を __変更できない__ というものがあります。これは、__先程のノート__ で __マークのパターン__ の __集合__ を例に挙げて __説明__ したように、__数学__ の __集合を扱う際__ に、一度 __集合の要素__ に __入れた__ ものの __内容__ を __後から変更する__ という処理を __行わない__ からです。

しかし、__set__ の __要素__ に __list__ のような __ハッシュ可能でない__、__ミュータブル__ なデータを __代入できてしまう__ と、__set__ に __対する処理__ によって __要素の値__ を __変更できなくても__、__list の要素__ を __変更__ することで、__間接的__ に __set の要素__ の __値__ を __変更できてしまう__ ことになります。

下記のプログラムは、実際に __実行するとエラー__ になりますが、__仮__ に __set の要素__ に、__list を代入できる__ 場合は、__間接的__ に __set__  の __要素の値__ を __変更できてしまいます__。

```python
a = [3, 4, 5] 
b = {1, 2, a} # a は list なので実際にはこの行を実行するとエラーになる
a[0] = 5      # 仮に上記でエラーが発生しない場合は、この処理で、b の要素の値を変更できてしまう
```

[以前の記事](https://qiita.com/ysgeso/items/3afe5630d7e615a28ebf#%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E5%8F%AF%E8%83%BD%E3%81%AA%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%81%AE%E7%A8%AE%E9%A1%9E)で説明したように、__ハッシュ可能なオブジェクト__ であれば、__上記__ のようなことは基本的には __起きない__[^3]ので __この問題__ は __発生しません__。

## set と list の比較

__set__ と __list__ は __性質が似ている__ ので、今回の記事で紹介した __set の性質__ に関して __list と比較__ したものを下記の表にまとめます。

|  | list | set |
|:--|:--|:--|
| __リテラルの外側の記号__  | `[` と `]` で要素を囲む  | `{` と `}` で要素を囲む  |
| __リテラルの要素の区切り__  | `,` で区切る  | list と同じ  |
| __空のデータ__  | `[]`  | `set()` |
| __内包表記の外側の記号__  | `[` と `]` で要素を囲む  | `{` と `}` で要素を囲む  |
| __扱えるのデータの種類__ | 任意のオブジェクト | ハッシュ可能なオブジェクト |
| __要素の順番__  | 順番がある  | 順番はない  |
| __要素の変更__  | 追加、削除、変更  | 追加、削除のみ  |
| __インデックスで参照できるか__  | 可能  | 不可能  |
| __要素に含まれるかの判定__  | `in`、`not in` 演算子  | list と同じ  |
| __`==` 演算子での `True` の判定__ | 順番も含めて等しい | 同じ要素を持つ |
| __演算子による演算__ | `+` `*` による結合 | <code>\|</code> `&` `-` `^` による集合演算 |
| __要素の追加のメソッド__  | `append`  | `add` |
| __要素の数を数える組み込み関数__  | `len`  | list と同じ |
| __要素の列挙__ | for 文により可能 | list と同じ |

# set を使った `ai8s` の実装

__set__ の __使い方__ を説明したので、次に、__set__ を使って処理を行うように __`ai8s`__ を __修正__ します。

## `enum_markpats` の修正

__`ai8s`__ が __set__ を __利用するため__ には、__`enum_markpats`__ が __返すデータ__ を、下記のプログラムのように __list__ から __set に修正__ する必要があります。__set__ と __list__ は __使い方__ が __かなり似ている__ ので、__下記の部分だけ__ を __修正__ するだけで済みます。

* __2 行目__：__`markpats`__ に __代入__ する値を、__空の list__ から __空の set__ に __修正__ する
* __7、9、12、15 行目__：__`append`__ メソッドを、__`add`__ メソッドに __修正__ する

```python
 1  def enum_markpats(self):
 2      markpats = set()
 3  
 4      # 横方向と縦方向の判定
 5      for i in range(self.BOARD_SIZE):
 6          count = self.count_marks(coord=[0, i], dx=1, dy=0)
 7          markpats.add(count)
 8          count = self.count_marks(coord=[i, 0], dx=0, dy=1)
 9          markpats.add(count)
10      # 左上から右下方向の判定
11      count = self.count_marks(coord=[0, 0], dx=1, dy=1)
12      markpats.add(count)
13      # 右上から左下方向の判定
14      count = self.count_marks(coord=[2, 0], dx=-1, dy=1)
15      markpats.add(count)
16
17      return markpats
18
19  Marubatsu.enum_markpats = enum_markpats
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def enum_markpats(self):
    markpats = set()
 
    # 横方向と縦方向の判定
    for i in range(self.BOARD_SIZE):
        count = self.count_marks(coord=[0, i], dx=1, dy=0)
        markpats.add(count)
        count = self.count_marks(coord=[i, 0], dx=0, dy=1)
        markpats.add(count)
    # 左上から右下方向の判定
    count = self.count_marks(coord=[0, 0], dx=1, dy=1)
    markpats.add(count)
    # 右上から左下方向の判定
    count = self.count_marks(coord=[2, 0], dx=-1, dy=1)
    markpats.add(count)

    return markpats

Marubatsu.enum_markpats = enum_markpats
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
def enum_markpats(self):
-   markpats = []
+   markpats = set()
 
    # 横方向と縦方向の判定
    for i in range(self.BOARD_SIZE):
        count = self.count_marks(coord=[0, i], dx=1, dy=0)
-       markpats.append(count)
+       markpats.add(count)
        count = self.count_marks(coord=[i, 0], dx=0, dy=1)
-       markpats.append(count)
+       markpats.add(count)
    # 左上から右下方向の判定
    count = self.count_marks(coord=[0, 0], dx=1, dy=1)
-   markpats.append(count)
+   markpats.add(count)
    # 右上から左下方向の判定
    count = self.count_marks(coord=[2, 0], dx=-1, dy=1)
-   markpats.append(count)
+   markpats.add(count)

    return markpats

Marubatsu.enum_markpats = enum_markpats
```
</details>

下記は、[前回の記事](https://qiita.com/ysgeso/items/58754ba98c286f414ea4#enum_markpats-%E3%81%AE%E5%AE%9F%E8%A3%85%E3%81%AE%E7%A2%BA%E8%AA%8D)で __`enum_markpats`__ の __実装__ を __確認__ する際に記述したプログラムです。このプログラムを実行すると、下記のような __エラーが発生__ します。

```python
mb = Marubatsu()

print(mb)
pprint(mb.enum_markpats())

mb.move(1, 1)
print(mb)
pprint(mb.enum_markpats())

mb.move(0, 0)
print(mb)
pprint(mb.enum_markpats())

mb.move(1, 0)
print(mb)
pprint(mb.enum_markpats())
```

実行結果
```
略
Cell In[33], line 7
      5 for i in range(self.BOARD_SIZE):
      6     count = self.count_marks(coord=[0, i], dx=1, dy=0)
----> 7     markpats.add(count)
      8     count = self.count_marks(coord=[i, 0], dx=0, dy=1)
      9     markpats.add(count)

TypeError: unhashable type: 'collections.defaultdict'
```

:::note
上記のエラーメッセージは、以下のような意味を持ちます。

* __SyntaxError__
データ型（type）に関するエラー
* __unhashable type: 'collections.defaultdict'__
collections モジュールの defaultdict は、ハッシュ可能（hashable）なデータ型（type）ではない（un）
:::

この __エラー__ は、__ハッシュ可能でない__、__defaultdict__ を __set の要素__ として __追加__ しようとしたことが原因です。従って、この __エラー__ を __修正__ するためには、__ハッシュ可能なオブジェクト__ を __返す__ ように、__`count_marks`__ を __修正__ する __必要__ があります。

# 今回の記事のまとめ

長くなりましたので、今回の記事はここまでにし、修正は次回の記事で行うことにします。なお、上記の __`enum_markpats`__ には __バグがある__ ので、__`marubatsu.py`__ には __反映させません__。

今回の記事では、__集合__ を扱う __データ型__ である __set__ に関する __説明__ を行いました。また、__set__ を使って __`ai8s`__ を __修正__ する際に __エラーが発生する__ ことを説明しました。

# 本記事で入力したプログラム

以下のリンクから、本記事で入力して実行した JupyterLab のファイルを見ることができます。

https://github.com/ysgeso/marubatsu/blob/master/052/marubatsu.ipynb

今回の記事では marubatsu.py と ai.py は変更していません。

# 次回の記事

https://qiita.com/ysgeso/items/af8b5dda0ddffd5c6d13

[^1]:違っていれば指摘していただければ嬉しいです
[^2]:__オペランド__（operand）とは、__演算子__ が __演算の対象__ とする __値__ のことです
[^3]:正確には、__例外__ として、__自分で定義__ した __クラス__ の __インスタンス__ の場合は __間接的__ にその __属性の値__ を __変更できる__ ので、__その点に注意__ する __必要__ があります