数据结构与算法 / 系统课时
集合与序列
集合与序列
本课建立算法语言中最常用的数学对象:集合用于表达“有哪些元素”,序列用于表达“元素按什么顺序出现”,多重集合则保留重复次数。理解这些差异后,你可以更准确地描述输入、状态、索引与计数问题。
学习目标
- 区分集合、子集、笛卡尔积、序列和多重集合
- 使用成员关系、基数和有序对描述算法对象
- 根据是否需要顺序与重复次数选择合适的数据模型
集合:只关心成员
集合是若干互不重复元素组成的整体,通常写成 。元素 属于集合 记为 ,不属于记为 。集合不记录元素出现顺序,重复写入同一元素也不会改变集合。
空集合记为 。集合中不同元素的数量称为基数,记为 。当集合 的每个元素都属于集合 时,称 是 的子集,记为 。若同时满足 ,则称为真子集。
两个集合相等的条件是它们包含完全相同的元素,与书写顺序无关。例如 与 表示同一个集合。
笛卡尔积:组合两个集合
集合 与集合 的笛卡尔积由所有有序对 组成,其中 且 ,记为 。有序对强调位置,因此 通常不等于 。
设 ,,则 包含 、、 和 。有限集合满足 。
笛卡尔积常用于描述坐标、状态组合、图中的边和多维搜索空间。例如简单有向图的边可用有序顶点对表示,简单无向图的每条边是两个不同顶点组成的无序集合。若允许自环或平行边,要另说明边的表示。任一因子为空时,笛卡尔积为空。
序列:顺序与重复都重要
序列是一组按位置排列的元素,通常写成 。序列长度为 ,同一个值可以出现多次,交换两个位置通常会得到不同序列。
数组、字符串、操作日志和算法输入往往天然是序列。序列给元素定义位置,具体访问开销取决于实现。因此“第一个元素”“前缀”“连续子段”等概念都有明确含义。子序列从原序列中删除若干元素后仍保持剩余元素的相对顺序,但不要求位置连续;子串或子数组通常要求连续。

多重集合:保留出现次数
多重集合不强调顺序,但允许同一元素出现多次。元素 在多重集合 中的出现次数可记为 。例如,单词序列“to be or not to be”对应的多重集合中,to 与 be 的重数都是 2。
多重集合适合描述频率统计、库存数量、字符计数和重复键集合。它与序列的区别在于:多重集合只保留每种元素出现多少次,不保留每次出现的位置。
| 数据模型 | 是否保留顺序 | 是否允许重复 | 典型用途 |
|---|---|---|---|
| 集合 | 否 | 否 | 去重、成员判断、访问标记 |
| 序列 | 是 | 是 | 数组、字符串、执行记录 |
| 多重集合 | 否 | 是 | 频率、库存、字符计数 |
算法中的选择原则
当问题只关心元素是否出现时,使用集合模型最自然,例如记录图搜索中已经访问的顶点。当问题依赖先后次序或位置时,应使用序列,例如排序算法的输入数组。当问题只关心重复次数而不关心位置时,多重集合更直接,例如判断两个字符串是否由相同字符及相同数量组成。
不要把数学模型与具体数据结构完全等同。数学上的集合可以由哈希表、平衡树或位图实现;序列可以由数组、链表或其他结构实现。模型回答“要表达什么”,数据结构回答“如何高效实现”。
用同一输入核对三种相等
按“序列相等、成员相等、重数相等”的顺序输出。Python 的 set 元素和 Counter 键需要可哈希。用 Counter 从序列直接计数即可表示本例的重数,手工填入负计数时已超出普通多重集合的定义。
from collections import Counter
from itertools import product
a = [3, 1, 3, 2, 1]
b = [1, 2, 3, 3, 1]
c = [1, 2, 3]
for other in (b, c):
print(a == other, set(a) == set(other), Counter(a) == Counter(other))
pairs = set(product((0, 1), ("x", "y", "z")))
print(len(pairs), (0, "x") in pairs, ("x", 0) in pairs)比较 b 的结果是 False、True、True。比较 c 则是 False、True、False。末行 6、True、False 验证有序对 (0, x) 属于 A × B,交换后不属于。
常见错误
- 把集合的书写顺序当成语义的一部分。集合只比较成员,不比较排列。
- 把子序列误认为连续片段。子序列保持相对顺序,但元素之间可以有间隔。
- 用集合处理需要计数的问题。集合会丢失重复次数,此时应使用多重集合或频率映射。
- 忽略笛卡尔积中有序对的方向。对于不同集合, 与 通常不是同一个集合。
本课练习
- 给定序列 ,分别写出它对应的集合和多重集合,并说明两种表示各自丢失了哪些信息。
- 设 ,,列出 的全部元素,计算其基数,并判断 是否属于该笛卡尔积。
- 为“网站访问用户去重”“按时间保存请求日志”“统计每个错误码出现次数”分别选择集合、序列或多重集合,并写出选择理由。
本课总结
- 集合保留成员关系,序列保留位置顺序,多重集合保留元素重数。
- 子集用于表达包含关系,笛卡尔积用于构造有序组合。
- 先确定数学模型,再选择满足性能需求的具体数据结构。
下一课预告
下一课将学习“函数与映射”,重点理解定义域、陪域、像,以及单射、满射、双射和复合函数如何描述算法中的转换关系。