恰好够用的集合论 – 集合运算（第 2 部分，共 3 部分）

欢迎来到这个三部分集合论系列文章的第二部分。第一篇文章《集合论定义》（最近已更新代码示例）详细介绍了必需的基础知识。强烈建议读者如果尚未阅读，请从那里开始。

本系列的第一个帖子介绍了集合，并展示了 ES6 数组与集合的相似之处。它还说明了如何将一个集合转换或映射为另一个相关的集合。本文通过探讨集合运算来扩展集合论。

注意：所有代码示例均以 ES6 编写，因此可能无法直接在浏览器中执行。最佳选择是使用 Node 或使用 Babel 或 TypeScript 进行转译。可用的工作代码位于 GitHub 上，并附有执行说明。

空集

空集是一个相当平凡的话题，但仍然值得一提。顾名思义，它们是没有元素的集合。它们也通常被称为零集。在数学上，空集表示为 \(\emptyset\) 或 \(\{ \}\)。这个概念与软件中的空数组有关。

基数

“基数”这个词听起来很厉害；然而，它仅仅是一个集合中的元素数量。包含三个元素的集合的数学表示如图 图一 – 基数 所示。

在 JavaScript 中，数组的基数是其长度。请参阅下面的代码

const someSet = [1, 2, 3, 4, 5]; 
const cardinality = someSet.length; 
// cardinality = 5

子集

子集相对容易解释，但具有深远的影响。子集是更大集合的一部分。例如，考虑所有动物的集合（\(A\)）。所有狗的集合（\(D\)）是动物集合的子集，因为虽然并非所有动物都是狗，但所有狗都是动物。子集的数学表示如下：\(D \subseteq A\)。另一种数学表达子集关系的方式是 \(\forall x(x \in D \rightarrow x \in A)\)。这看起来很奇怪，但前提是对于 \(D\) 中的每一个（\(\forall\)）元素（\(x\)），都意味着（\(\rightarrow\)）该元素（\(x\)）也存在于 \(A\) 中。

子集通常与维恩图一起讲授。请参阅 图三 – 维恩图 示例。诚然，这里对子集的描述有些平淡。然而，本系列的最后一篇文章将严重依赖这个概念，因此值得在此详细阐述。

ES6 在数组对象上有一个内置的 filter 方法，可以轻松访问子集。Filter 将一个谓词作为参数。回想第一篇文章，谓词是一个函数，它接受单个参数并返回一个布尔值响应。Filter 方法将谓词应用于集合中的每个项，并创建一个新的集合，其中包含谓词返回 true 的项。请参阅下面的代码

const animals = [
    {name: "Tom", type: "Cat"},
    {name: "Jerry", type: "Mouse"},
    {name: "Pluto", type: "Dog"},
    {name: "Scooby Doo", type: "Dog"}];

const dogs = animals.filter(a => a.type == "Dog");
// dogs = [{name: "Pluto", type: "Dog"}, {name: "Scooby Doo", type: "Dog"}]

求和

“求和”这个词有点误导，因为它暗示着简单地将元素相加，然而它是一个更强大的概念。求和将一个函数应用于集合中的每个元素，将其简化为一个单一的值。\(\sum_{x \in S}f(x)\) 是表示该算法的数学符号，其中 \(S\) 是任何集合，\(f(x)\) 是任何函数。请看 图四 – 求和。给定集合 \(A\)，集合中的每个元素都乘以二并相加。

ES6 的数组对象的 reduce 方法与求和类似。顾名思义，reduce 将一个函数应用于集合的每个成员，将其简化为一个单一的值。它接受两个参数：一个函数和一个可选的起始值。该函数接受一个累加值和一个当前项。处理完所有项后，累加值的状态就是最终返回值。下面的代码是 图四 – 求和 中详述的相同过程。

const someSet = [1, 2, 3];
const sum = someSet.reduce((acc, x) => acc + x * 2, 0);
// sum = 12

Reduce 对于许多超出数学函数范围的操作都很有用。下面的代码使用它从用户集合中提取电子邮件地址。

const users = [
    {id: 1, email: "email@email.com"},
    {id: 2, email: "email2@email2.com"}, 
    {id: 3, email: "email3@email.com"}];

const emails = users.map(u => u.email).reduce((acc, x) => `${acc};${x}`);
// emails = "email@email.com;email2@email2.com;email3@email.com"

上面并未充分体现 reduce 方法的优点，因为它的功效几乎是无限的。还有许多其他选项超出了本文的范围。强烈鼓励读者在 Mozilla 的优秀 JavaScript 参考 中查找更多信息。

幂集

幂集是每个程序员在其职业生涯的某个时候都必须处理的事情，即使他们无法以正式的名称识别它们。在数学术语中，幂集表示为 \(P(A)\)。幂集是所有子集的集合，包括空集本身：更简洁地说，是所有可能的集合组合。幂集总是包含 \(2^n\) 个元素，其中 \(n\) 是原始集合的基数（\(|P(A)|=2^(|A|)\)）。

在没有示例的情况下，幂集很难概念化。图五 – 幂集 描绘了一个包含三个元素的集合。幂集是这三个元素的所有可能组合。结果是一个基数为八（\(2^3\)）的集合。

不幸的是，JavaScript 没有内置的创建幂集的方法。然而，只要有创意，这是一个很容易解决的问题。请参阅下面的代码

const someSet = [0, 1, 2];
const powerSet = someSet.reduce((acc, x) => [...acc, ...acc.map(y => [x, ...y])], [[]]);
// powerSet = [[], [0], [1], [1,0], [2], [2,0], [2,1], [2,1,0]]

上面的代码乍一看可能有点吓人，所以它值得进一步解释。幂集总是包含一个空集，因此 reduce 方法的第二个参数是一个只包含该空集的集合。这是起始值。当函数作用于集合中的第一个项时，acc 的值为 [[]]，x 的值为 0。将当前项连接到 acc 中的每一项的结果连接到 acc 的值上，使其变为 [[], [0]]。相同的算法应用于集合中的每一项。这很难想象，所以下面的代码详细说明了调用时实际发生的情况。

const ps = (acc, x) => [...acc, ...acc.map(y => [x, ...y])]; 

// First element
let acc = ps([[]], 0);
// acc = [[], [0]]

// Second element
acc = ps(acc, 1);
// acc = [[], [0], [1], [1,0]]

// Third element
acc = ps(acc, 2);
// acc = [[], [0], [1], [1, 0], [2], [2, 0], [2, 1], [2, 1, 0]]

强烈鼓励读者多次回顾本节，直到概念清晰为止。

结论

本文概述了几种有用的集合运算。ES6 使用 reduce 方法将求和的概念应用于集合。幂集是所有可能集合组合的集合。虽然没有内置的 ES6 功能来实现这一点，但它是一个易于创建的算法。请务必回来阅读最后一篇文章，题为《集合的碰撞》。这是本系列中最有用的文章，它涵盖了作用于多个独立集合的集合运算。

CodeProject