数据结构与算法 / 系统课时

集合与序列

集合与序列

本课建立算法语言中最常用的数学对象:集合用于表达“有哪些元素”,序列用于表达“元素按什么顺序出现”,多重集合则保留重复次数。理解这些差异后,你可以更准确地描述输入、状态、索引与计数问题。

学习目标

  • 区分集合、子集、笛卡尔积、序列和多重集合
  • 使用成员关系、基数和有序对描述算法对象
  • 根据是否需要顺序与重复次数选择合适的数据模型

集合:只关心成员

集合是若干互不重复元素组成的整体,通常写成 A={1,2,3}A = \{1, 2, 3\}。元素 xx 属于集合 AA 记为 x∈Ax \in A,不属于记为 x∉Ax \notin A。集合不记录元素出现顺序,重复写入同一元素也不会改变集合。

空集合记为 ∅\varnothing。集合中不同元素的数量称为基数,记为 ∣A∣|A|。当集合 AA 的每个元素都属于集合 BB 时,称 AA 是 BB 的子集,记为 A⊆BA \subseteq B。若同时满足 A≠BA \neq B,则称为真子集。

两个集合相等的条件是它们包含完全相同的元素,与书写顺序无关。例如 {1,2,3}\{1, 2, 3\} 与 {3,1,2}\{3, 1, 2\} 表示同一个集合。

笛卡尔积:组合两个集合

集合 AA 与集合 BB 的笛卡尔积由所有有序对 (a,b)(a, b) 组成,其中 a∈Aa \in A 且 b∈Bb \in B,记为 A×BA \times B。有序对强调位置,因此 (a,b)(a, b) 通常不等于 (b,a)(b, a)。

设 A={red,blue}A = \{\text{red}, \text{blue}\},B={1,2}B = \{1, 2\},则 A×BA \times B 包含 (red,1)(\text{red}, 1)、(red,2)(\text{red}, 2)、(blue,1)(\text{blue}, 1) 和 (blue,2)(\text{blue}, 2)。有限集合满足 ∣A×B∣=∣A∣⋅∣B∣|A \times B| = |A| \cdot |B|。

笛卡尔积常用于描述坐标、状态组合、图中的边和多维搜索空间。例如简单有向图的边可用有序顶点对表示,简单无向图的每条边是两个不同顶点组成的无序集合。若允许自环或平行边,要另说明边的表示。任一因子为空时,笛卡尔积为空。

序列:顺序与重复都重要

序列是一组按位置排列的元素,通常写成 S=⟨a1,a2,…,an⟩S = \langle a_1, a_2, \ldots, a_n \rangle。序列长度为 nn,同一个值可以出现多次,交换两个位置通常会得到不同序列。

数组、字符串、操作日志和算法输入往往天然是序列。序列给元素定义位置,具体访问开销取决于实现。因此“第一个元素”“前缀”“连续子段”等概念都有明确含义。子序列从原序列中删除若干元素后仍保持剩余元素的相对顺序,但不要求位置连续;子串或子数组通常要求连续。

集合、序列与多重集合的结构对比

多重集合:保留出现次数

多重集合不强调顺序,但允许同一元素出现多次。元素 xx 在多重集合 MM 中的出现次数可记为 mM(x)m_M(x)。例如,单词序列“to be or not to be”对应的多重集合中,to 与 be 的重数都是 2。

多重集合适合描述频率统计、库存数量、字符计数和重复键集合。它与序列的区别在于:多重集合只保留每种元素出现多少次,不保留每次出现的位置。

数据模型 是否保留顺序 是否允许重复 典型用途
集合 否 否 去重、成员判断、访问标记
序列 是 是 数组、字符串、执行记录
多重集合 否 是 频率、库存、字符计数

算法中的选择原则

当问题只关心元素是否出现时,使用集合模型最自然,例如记录图搜索中已经访问的顶点。当问题依赖先后次序或位置时,应使用序列,例如排序算法的输入数组。当问题只关心重复次数而不关心位置时,多重集合更直接,例如判断两个字符串是否由相同字符及相同数量组成。

不要把数学模型与具体数据结构完全等同。数学上的集合可以由哈希表、平衡树或位图实现;序列可以由数组、链表或其他结构实现。模型回答“要表达什么”,数据结构回答“如何高效实现”。

用同一输入核对三种相等

按“序列相等、成员相等、重数相等”的顺序输出。Python 的 set 元素和 Counter 键需要可哈希。用 Counter 从序列直接计数即可表示本例的重数,手工填入负计数时已超出普通多重集合的定义。

python
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,交换后不属于。

常见错误

  1. 把集合的书写顺序当成语义的一部分。集合只比较成员,不比较排列。
  2. 把子序列误认为连续片段。子序列保持相对顺序,但元素之间可以有间隔。
  3. 用集合处理需要计数的问题。集合会丢失重复次数,此时应使用多重集合或频率映射。
  4. 忽略笛卡尔积中有序对的方向。对于不同集合,A×BA \times B 与 B×AB \times A 通常不是同一个集合。

本课练习

  1. 给定序列 ⟨3,1,3,2,1⟩\langle 3, 1, 3, 2, 1 \rangle,分别写出它对应的集合和多重集合,并说明两种表示各自丢失了哪些信息。
  2. 设 A={0,1}A = \{0, 1\},B={x,y,z}B = \{x, y, z\},列出 A×BA \times B 的全部元素,计算其基数,并判断 (x,0)(x, 0) 是否属于该笛卡尔积。
  3. 为“网站访问用户去重”“按时间保存请求日志”“统计每个错误码出现次数”分别选择集合、序列或多重集合,并写出选择理由。

本课总结

  • 集合保留成员关系,序列保留位置顺序,多重集合保留元素重数。
  • 子集用于表达包含关系,笛卡尔积用于构造有序组合。
  • 先确定数学模型,再选择满足性能需求的具体数据结构。

下一课预告

下一课将学习“函数与映射”,重点理解定义域、陪域、像,以及单射、满射、双射和复合函数如何描述算法中的转换关系。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

集合与序列

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通