生成组合对象的算法之生成子集

type

Post

status

Published

date

Feb 13, 2026

slug

creatset

summary

内容围绕生成子集的基础概念与相关编码方法展开，说明幂集由元素“取或不取”的二元性决定，n个元素共有2^n个子集；同时解释字典序依赖既定顺序，并给出格雷码的反射递归构造与Gi=i^(i>>1)的直接计算公式。

category

笔记

icon

password

ai_summary

何为幂集？

数学概念。
指一个集合的所有子集，包括空集和它自身所构成的集合。

📌

例子：

A = {1,2}

幂集 P(A) 为：{ ∅, {1}, {2}, {1, 2} }

为何一个集合n个元素，那么它的幂集就有个元素

直接源于 每个元素在子集中的“存在”或“不存在”这一根本的二元性。
这种“是/否”、“开/关”、“0/1”的思维，也是它在计算机科学（如位运算、状态表示）和逻辑学中如此重要的原因。

字典序？

像在字典里面查单词那样进行排序的规则。
从左到右，诸位比较的原则。简单来说，字典序就是一种“先比第一位，第一位相同再比下一位”的、非常符合人类直觉的排序方法。
一个关键点：

字典序依赖于元素的既定顺序。
对于英文字母，顺序是 a, b, c, ... , z；
对于数字，顺序是 0, 1, 2, ... , 9。如果元素本身没有天然顺序，则需要先定义顺序规则。

例子：

比较 "apple"和 "banana"：先看第一个字母，a< b，所以 "apple"排在 "banana"前面———元素大的在前面。

比较 "cat"和 "catalog"：前三个字母 "cat"都相同，但第一个词已经结束，而第二个词还有字母。因此，较短的 "cat"排在较长的 "catalog"前面———短序列在前面。

因此之所以可以用来输出有序可预测组合，就是因为字典序这种特性。

挤压序（squashed order）？

对于集合 {}的子集：

所有包含aj的子集必须紧排在a1,…,aj-1的子集之后。
“包含”指子集中至少含有该元素，“紧排”意味着在序列中这些子集连续出现，并且直接跟在指定子集组的后面。

生成挤压序的算法思路

递归法
迭代法

二进制反射格雷码？

一种特殊的二进制编码序列，其核心特性是相邻的两个编码之间以及首尾之间只有一位二进制数字不同。
何为反射倒序？

“反射倒序”就是像照镜子一样把序列颠倒过来。在格雷码构造中，这个操作确保了新生成序列的中间衔接处和首尾循环处，都能完美满足“每次只变一位”的严格条件。
例如，序列 [A, B, C, D]的倒序就是 [D, C, B, A]。反射它不仅仅是倒序，更强调这种首尾对称、一一对应的镜像关系。

构造方法：

“反射”构造法-构造过程是递归的：:

基础：1位格雷码，即[0,1]。
递归步骤(n > 1)：

生成n-1位格雷码序列。
列出序列正序，并在每个序列前加0。此为新序列上半部分。
列出序列倒序(即反射)，并在每个序列前加1，此为新序列下半部分。

将上下部分连起来即为n位格雷码序列。
用公式表达这个递归：

公式法（直接计算）：

对于任意一个顺序编号 i（从0开始），它对应的n位格雷码 G(i)可以直接通过公式计算得出，无需生成整个序列：
G(i) = i ^ (i >> 1),其中 ^表示按位异或，>>是右移。这个公式非常高效，是工程中最常用的方法。

📖

例子

基础：1位格雷码序列：[0, 1]

1位格雷码生成 2位格雷码：

2位格雷码生成： -- 步骤1： ---- 在1位码[0, 1]前加0 (正序加0) ---- 0+ [0, 1]=> [00, 01]（这是上半部分） -- 步骤2： ---- 在1位码前加1 (反射倒序，加1) ---- 先对[0, 1]进行反射倒序，得到 [1, 0]。 ---- 然后给每个前面加 1：1+ [1, 0]=> [11, 10]（这是下半部分）

连接后得到： 00, 01, 11, 10

3位格雷码生成：

步骤1：在2位码前加0 (正序) --- 0 + [00, 01, 11, 10] => [000,001,011,010] 步骤2：在2位码前加1 (反射倒序) --- 先[00, 01, 11, 10] 取反射倒序：[10,11,01,00] --- 然后给每个前面加 1：1+[10,11,01,00]=> [110,111,101,100]

连接后得到： 000, 001, 011, 010, 110, 111, 101, 100

👋 欢迎来访！