博客详情 - whoj

chjshen 的博客
数学-组合数学之集合&离散
chjshen 教练 LV 5 SU @ 2023-6-1 8:05:05

集合的概念

二进制集合操作

一个数的二进制表示可以看作是一个集合（ $0$ 表示不在集合中， $1$ 表示在集合中）。比如集合 $\{1,3,4,8\}$ ，可以表示成 $(100011010)_2$ 。而对应的位运算也就可以看作是对集合进行的操作。

操作	集合表示	位运算语句
交集	$a \cap b$	`a & b`
并集	$a \cup b$	a
补集	$\bar{a}$	`~a` （全集为二进制都是 1）
差集	$a \setminus b$	`a & (~b)`
对称差	$a\triangle b$	`a ^ b`

在进一步介绍集合的子集遍历操作之前，先看位运算的有关应用例子。

模 2 的幂

一个数对 $2$ 的非负整数次幂取模，等价于取二进制下一个数的后若干位，等价于和 $mod-1$ 进行与操作。

// C++ Version
int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }

于是可以知道， $2$ 的非负整数次幂对它本身取模，结果为 $0$ ，即如果 $n$ 是 $2$ 的非负整数次幂， $n$ 和 $n-1$ 的与操作结果为 $0$ 。

事实上，对于一个正整数 $n$ ， $n-1$ 会将 $n$ 的最低 $1$ 位置零，并将后续位数全部置 $1$ 。因此， $n$ 和 $n-1$ 的与操作等价于删掉 $n$ 的最低 $1$ 位。

借此可以判断一个数是不是 $2$ 的非负整数次幂。当且仅当 $n$ 的二进制表示只有一个 $1$ 时， $n$ 为 $2$ 的非负整数次幂。

// C++ Version
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

子集遍历

遍历一个二进制数表示的集合的全部子集，等价于枚举二进制数对应掩码的所有子掩码。

掩码是一串二进制码，用于和源码进行与运算，得到屏蔽源码的若干输入位后的新操作数。

掩码对于源码可以起到遮罩的作用，掩码中的 $1$ 位意味着源码的相应位得到保留，掩码中的 $0$ 位意味着源码的相应位进行置 $0$ 操作。将掩码的若干 $1$ 位改为 $0$ 位可以得到掩码的子掩码，掩码本身也是自己的子掩码。

给定一个掩码 $m$ ，希望有效迭代 $m$ 的所有子掩码 $s$ ，可以考虑基于位运算技巧的实现。

// 降序遍历 m 的非空子集
int s = m;
while (s > 0) {
  // s 是 m 的一个非空子集
  s = (s - 1) & m;
}

或者使用更紧凑的 for 语句：

// 降序遍历 m 的非空子集
for (int s = m; s; s = (s - 1) & m)
// s 是 m 的一个非空子集

这两段代码都不会处理等于 $0$ 的子掩码，要想处理等于 $0$ 的子掩码可以使用其他办法，例如：

// 降序遍历 m 的子集
for (int s = m;; s = (s - 1) & m) {
  // s 是 m 的一个子集
  if (s == 0) break;
}

接下来证明，上面的代码访问了所有 $m$ 的子掩码，没有重复，并且按降序排列。

假设有一个当前位掩码 $s$ ，并且想继续访问下一个位掩码。在掩码 $s$ 中减去 $1$ ，等价于删除掩码 $s$ 中最右边的设置位，并将其右边的所有位变为 $1$ 。

为了使 $s-1$ 变为新的子掩码，需要删除掩码 $m$ 中未包含的所有额外的 $1$ 位，可以使用位运算 $(s-1)\&m$ 来进行此移除。

这两步操作等价于切割掩码 $s-1$ ，以确定算术上可以取到的最大值，即按降序排列的 $s$ 之后的下一个子掩码。

因此，该算法按降序生成该掩码的所有子掩码，每次迭代仅执行两个操作。

特殊情况是 $s=0$ 。在执行 $s-1$ 之后得到 $-1$ ，其中所有位都为 $1$ 。在 $(s-1)\&m$ 操作之后将得到新的 $s$ 等于 $m$ 。因此，如果循环不以 $s=0$ 结束，算法的循环将无法终止。

使用 $\text{popcount}(m)$ 表示 $m$ 二进制中 $1$ 的个数，用这种方法可以在 $O(2^{\text{popcount}(m)})$ 的时间复杂度内遍历集合 $m$ 的子集。

遍历所有掩码的子掩码

在使用掩码动态编程的问题中，有时会希望对于每个掩码，遍历掩码的所有子掩码：

for (int m = 0; m < (1 << n); ++m)
  // 降序遍历 m 的非空子集
  for (int s = m; s; s = (s - 1) & m)
// s 是 m 的一个非空子集

这样做可以遍历大小为 $n$ 的集合的每个子集的子集。

接下来证明，该操作的时间复杂度为 $O(3^n)$ ， $n$ 为掩码总共的位数，即集合中元素的总数。

考虑第 $i$ 位，即集合中第 $i$ 个元素，有三种情况：

在掩码 $m$ 中为 $0$ ，因此在子掩码 $s$ 中为 $0$ ，即元素不在大小子集中。
在 $m$ 中为 $1$ ，但在 $s$ 中为 $0$ ，即元素只在大子集中，不在小子集中。
在 $m$ 和 $s$ 中均为 $1$ ，即元素同时在大小子集中。

总共有 $n$ 位，因此有 $3^n$ 个不同的组合。

还有一种证明方法是：

如果掩码 $m$ 具有 $k$ 个 $1$ ，那么它有 $2^k$ 个子掩码。对于给定的 $k$ ，对应有 $C_n^k$ 个掩码 $m$ ，那么所有掩码的总数为：

\sum_{k=0}^n C_n^k 2^n

上面的和等于使用二项式定理对 $(1+2)^n$ 的展开，因此有 $3^n$ 个不同的组合。

离散简介

离散化本质上可以看成是一种哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。

通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。

用来离散化的可以是大整数、浮点数、字符串等等。

实现

C++ 离散化有现成的 STL 算法：

离散化数组

将一个数组离散化，并进行查询是比较常用的应用场景：

// a[i] 为初始数组,下标范围为 [1, n]
// len 为离散化后数组的有效长度
std::sort(a + 1, a + 1 + n);

len = std::unique(a + 1, a + n + 1) - a - 1;
// 离散化整个数组的同时求出离散化后本质不同数的个数。

在完成上述离散化之后可以使用 std::lower_bound 函数查找离散化之后的排名（即新编号）：

std::lower_bound(a + 1, a + len + 1, x) - a;  // 查询 x 离散化后对应的编号

同样地，我们也可以对 vector 进行离散化：

// std::vector<int> a, b; // b 是 a 的一个副本
std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());
for (int i = 0; i < n; ++i)
  b[i] = std::lower_bound(a.begin(), a.end(), b[i]) - a.begin();

数学-组合数学之集合&离散