1 集合的基本概念
在计算机科学中，集合（collection)是一组可变数量的数据项（也可能是0个）的组合，这些数据项可能共享某些特征，需要以某种操作方式一起进行操作。一般来讲，这些数据项的类型是相同的，或基类相同（若使用的语言支持继承）。列表（或数组）通常不被认为是集合，因为其大小固定，但事实上它常常在实现中作为某些形式的集合使用。
集合(collection)的种类包括列表，集，多重集，树和图。枚举类型可以是列表或集。
2 集合（集）set
2.1 set的基本概念
与列表不同，在集（set)中，数据项是无序的，也不允许存在相同数据项。集(set)支持添加、删除和查找项目。一些语言内建对集(set)的支持，而在其它语言中，可以利用散列表实现集。Python中内建支持set类型。
set是 可变的、无序的、不重复 的元素的集合
2.2 set的定义、初始化
- set() -> new empty set object
- set(iterable) -> new set object
In [1]: s1 = set()
In [2]: s1
Out[2]: set()
In [3]: s2 = set(range(5))
In [4]: s2
Out[4]: {0, 1, 2, 3, 4}
In [5]: s3 = set(list(range(10)))
In [6]: s3
Out[6]: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
In [7]: s4 = {} #这实际上定义了一个新字典
#In [14]: type(s4)
#Out[14]: dict
In [8]: s4
Out[8]: {} #这是一个空字典
In [9]: s5 = {9,10,11}
In [10]: s5
Out[10]: {9, 10, 11}
In [11]: s6 = {(1,2),3,'a'}
In [12]: s6
Out[12]: {(1, 2), 3, 'a'}
In [13]: s7 = {[1],(1,),1}
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-13-aa063e638452> in <module>
----> 1 s7 = {[1],(1,),1}
TypeError: unhashable type: 'list'
由以上可知，在定义、初始化一个set的时候，有几点要注意。
- set的元素要求必须可以hash,不可hash的元素加入set会报错TypeError
- set是无序的，元素不可以使用索引
- set可以迭代
- {}代表一个空字典，set不能像元组、列表、字符串一样只需要在符号（如中括号，小括号，引号）中留空来定义一个空容器
2.3 set元素的增加
- add(element)
- 增加一个元素到set中
- 如果元素存在，则什么都不做
In [17]: s1 = {1,2,3,4,5,6,7,8,9}
In [18]: s1.add(9)
In [19]: s1
Out[19]: {1, 2, 3, 4, 5, 6, 7, 8, 9}
In [20]: s1.add(99)
In [21]: s1
Out[21]: {1, 2, 3, 4, 5, 6, 7, 8, 9, 99}
- update(*others)
- 合并其他元素到set中来
- 参数others必须是可迭代对象
- 就地修改
In [27]: s1 = {1,2,3,4,5}
In [28]: s1.update(range(8))
In [29]: s1
Out[29]: {0, 1, 2, 3, 4, 5, 6, 7}
#由于set中的元素是不可复制的，这个操作实际上只增加了6，7两个元素
In [30]: s1.update(range(9),range(11,20))
In [31]: s1
Out[31]: {0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14, 15, 16, 17, 18, 19}
#update方法可以添加多个可迭代对象，一次把元素添加到set中去
2.4 set删除
- remove(element)
- 从set中移除一个元素
- 元素不存在，抛出KeyError异常。
In [1]: s1 = {1,2,3,4,5}
In [2]: s1.remove(5)
In [3]: s1
Out[3]: {1, 2, 3, 4}
#element存在，成功移除
In [4]: s1.remove(100)
#element不存在，报错KeyError
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
<ipython-input-4-685aafef4353> in <module>
----> 1 s1.remove(100)
KeyError: 100
- discard(element)
- 从set中移除一个元素
- 元素不存在，什么都不做
In [7]: s1 = {1,2,3,4,5}
In [8]: s1.discard(1)
In [9]: s1
Out[9]: {2, 3, 4, 5}
#元素存在，移除成功
In [10]: s1.discard(100)
In [11]: s1
Out[11]: {2, 3, 4, 5}
#元素不存在，移除失败。无报错或其他任何操作
- pop() -> item
- 移除并返回任意元素
- 空集返回KeyError
因为set是无序的，无法指定索引，只能随机移除
In [12]: s1 = {1,2,3,4,5}
In [13]: s1.pop()
Out[13]: 1
#随机移除，返回移除值1
In [14]: s1 = set()
In [15]: s1.pop()
#s1为空集，无法移除，报错KeyError
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
<ipython-input-15-095118de218b> in <module>
----> 1 s1.pop()
KeyError: 'pop from an empty set'
- clear()
- 移除所有元素
In [16]: s1 = {1,2,3,4,5}
In [17]: s1.clear()
In [18]: s1
Out[18]: set()
2.5 set的修改、查询
- 修改
- 要么删除，要么加入新的元素
set是无序的，无法通过索引指定某一个元素进行修改。所以只有先删除后增加的操作。事实上，修改这个词也只有在有序容器中才有意义，set内部元素本身无序，不存在修改的。
- 查询
- 非线性结构，无法查询
- 遍历
- 可以迭代所有元素
In [24]: s1 = {1,2,3,4,5}
In [25]: for i in s1:
...: print(i)
...:
1
2
3
4
5
虽然set是无序的，但是仍然可以迭代。有序无序和可否迭代无关。
- 成员运算符
- in和not in可以判断元素是否在set中
In [26]: s1 = {1,2,3,4,5}
In [27]: 5 in s1
Out[27]: True
In [28]: 55 in s1
Out[28]: False
set中做成员运算符的操作和list相比，不用遍历，效率比较高
2.6 set和线性结构
线性结构的查询时间复杂度是O(n),即随着数据规模的增大而耗时
set、dict等结构，内部使用hash值作为key，时间复杂度可以做到O(1),查询时间和数据规模无关
- 可hash
数值型int,float,complex
布尔型True,False
字符串string，bytes
元组tuple
None
以上都是不可变类型，是可哈希类型，hashable
- set的元素必须是可hash的。（所以set不能成为set的元素）
3 集合运算
3.1 集合运算和集合的一些基本概念
- 全集
- 所有元素的集合。例如实数集，所有师叔组成的集合就是全集。
- 子集subset和超级superset
- 一个集合A所有元素都在另一个集合B内，A就是B的子集，B是A的超集
- 真子集和真超集
- A是B的子集，且A不等于B，则A是B的真子集，B是A的真超集
并集：多个集合合并的结果
交集：多个集合的公共部分
差集：集合中除去和其他集合的公共部分
3.2 集合运算
3.2.1并集
- 将两个集合A和B的所有的元素合并在一起，组成的集合称为集合A和集合B的并集
如韦恩图所示
union(*others)
返回和多个集合合并后的新的集合
In [29]: s1 = {1,2,3}
In [30]: s2 = {6,7,9}
In [31]: s1.union(s2)
Out[31]: {1, 2, 3, 6, 7, 9}
In [32]: s3 = {1,2,3}
In [33]: s1.union(s3)
Out[33]: {1, 2, 3}
- | 运算符重载
- 等同于union
In [34]: s1 = {1,2}
In [35]: s2 = {5,6}
In [36]: s1 |s2
Out[36]: {1, 2, 5, 6}
- update(*others)
- 和多个集合合并，就地修改
In [38]: s1 = {1,2}
In [39]: s2 = {'a','b'}
In [40]: s3 = {b'332'}
In [41]: s1.update(s2,s3)
In [42]: s1
Out[42]: {1, 2, 'a', 'b', b'332'}
- |=
- 等同于update
3.2.2 交集
-
集合A和B，由所有属于A且属于B的元素组成的集合image
intersection(*others)
- 返回和多个集合的交集
In [1]: s1 = set(range(10))
In [2]: s2 = {'a',3,4,7}
In [3]: s3 = {0}
In [4]: s1.intersection(s2,s3)
Out[4]: set()
# s1,s2,s3无共同交集，返回空集
In [1]: s1 = set(range(10))
In [2]: s2 = {'a',0,9,'sss'}
In [3]: s3 = {0,1,2,3,4,5,6,7}
In [4]: s1.intersection(s2,s3)
Out[4]: {0}
# s1,s2,s3有共同元素0，返回由0组成的集合
- &
- 等同于intersection
In [7]: s1 = set(range(10))
In [8]: s2 = set(range(5))
In [9]: s1 & s2
Out[9]: {0, 1, 2, 3, 4}
# s2 是s1的子集，返回了由s2中全部元素组成的集合
- intersection_update(*others)
- 获取和多个集合的交集，并就地修改
In [10]: s1 = {'a',1,2,3,4,5,6,7}
In [11]: s2 = set(range(1,5))
In [12]: s3 = {4,5,6,7,8,9,0}
In [13]: s1.intersection_update(s2,s3)
In [14]: s1
Out[14]: {4}
# s1已经被修改为之前的s1,s2,s3的交集
- &=
- 等同intersection_update
3.2.3 差集
-
集合A和B，由所有属于A且不属于B的元素组成的集合
image
- difference(*others)
- 返回和多个集合的差集
In [15]: s1 = set(range(15))
In [16]: s2 = set(range(7,10))
In [17]: s3 = {1,4,7,9,5}
In [18]: s1.difference(s2,s3)
Out[18]: {0, 2, 3, 6, 10, 11, 12, 13, 14}
# 返回了s1和s2、s3的差集
- 等同diffrence
- difference_update(*others)
- 获取和多喝集合的差集并就地修改
In [19]: s1 = set(range(15))
In [20]: s2 = set(range(7,10))
In [21]: s3 = {1,4,7,9,5}
In [22]: s1.difference_update(s2,s3)
In [23]: s1
Out[23]: {0, 2, 3, 6, 10, 11, 12, 13, 14}
#s1修改为s1和s2、s3的差集
In [28]: s1 = set(range(15))
In [29]: s2 = set(range(10))
In [30]: s3 = set(range(10,15))
In [31]: s1.difference_update(s2,s3)
In [32]: s1
Out[32]: set()
#当s1和s2、s3差集为空时，s1被修改为空集
- -=
- 等同于diffrence_update()
3.2.4 对称差集
-
集合A和B，由所有不属于A和B的交集元素组成的集合，记作(A - B)∪(B - A)
image sysmmetric_differece(other)
- 返回和另一个集合的对称差集
- ^
- 等同sysmmetric_differece()
In [33]: s1 = set(range(10))
In [34]: s2 = set(range(7,15))
In [35]: s1 ^ s2
Out[35]: {0, 1, 2, 3, 4, 5, 6, 10, 11, 12, 13, 14}
#返回的是A对B的差集和B对A的差集的并集
#如果A等于B返回空集
- sysmmetric_differece_update(other)
- 获取和另一个集合的对称差集并就地修改
- ^=
- 等同于sysmmetric_differece_update()
In [33]: s1 = set(range(10))
In [34]: s2 = set(range(7,15))
In [36]: s1 ^= s2
In [37]: s1
Out[37]: {0, 1, 2, 3, 4, 5, 6, 10, 11, 12, 13, 14}
#s1被修改为s1和s2的对称差集
3.3 集合运算的其他操作
- issubset(other)、 <=
- 判断当前集合是否是另外一个集合的子集
In [38]: s1 = set(range(7))
In [39]: s2 = {1,3,5}
In [40]: s2 <= s1
Out[40]: True
- set1 < set2
- 判断set1是否是set2的真子集
由于这些判断太简单了，就不贴代码了
issuperset(other)、 >=
判断当前集合是否是other的超集
set1 > set2
判断set1是否是set2的真超集
isdisjoint(other)
当前集合和另外一个集合是否由交集，没有交集，返回True
In [41]: s1 = set(range(10))
In [42]: s2 = {1,3,7}
In [43]: s1.isdisjoint(s2)
Out[43]: False
In [44]: s3 = {-1,-3}
In [45]: s1.isdisjoint(s3)
Out[45]: True
