type
Post
status
Published
date
Feb 13, 2026
slug
creatset
summary
tags
算法笔记
阅读笔记
category
笔记
icon
password
- 何为幂集？
- 数学概念。
- 指一个集合的所有子集，包括空集和它自身所构成的集合。
- 例子：
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),其中
^表示按位异或，>>是右移。这个公式非常高效，是工程中最常用的方法。 - 例子
- Author:RHZ
- URL:http://www.rhzhz.cn/article/creatset
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
