关于子序列 - CLRS
Regarding subsequences - CLRS
我正在阅读 CLRS 的第 15 章，发现了子序列的定义：
A subsequence of a given sequence is just the given sequence with zero
or more elements left out.
后来说：
Each subsequence of X corresponds to a subset of the indices {1, 2,
3...m} of X. Because X has 2^m subsequences...
我不明白 X 怎么会有 2^m 个子序列。据我了解，如果
X = {A, B}，那么 X 的子序列可以是 {A}、{B} 和 {A, B} 所以我们有 3 个子序列而不是 2^2。有人可以告诉我我在这里缺少什么吗？
有一个空子集。
对于任何集合S，S的幂集是可能的子集数，即2^|S|哪里|s|是集合的基数，即集合中元素的数量。
在你的例子中，序列只是一个集合，可能的子序列数等于序列的幂集。
在你的例子中 X = {A, B} 可能的子序列是 {empty, A, B ,AB}
我正在阅读 CLRS 的第 15 章，发现了子序列的定义：
A subsequence of a given sequence is just the given sequence with zero or more elements left out.
后来说：
Each subsequence of X corresponds to a subset of the indices {1, 2, 3...m} of X. Because X has 2^m subsequences...
我不明白 X 怎么会有 2^m 个子序列。据我了解，如果
X = {A, B}，那么 X 的子序列可以是 {A}、{B} 和 {A, B} 所以我们有 3 个子序列而不是 2^2。有人可以告诉我我在这里缺少什么吗？
有一个空子集。
对于任何集合S，S的幂集是可能的子集数，即2^|S|哪里|s|是集合的基数，即集合中元素的数量。
在你的例子中，序列只是一个集合，可能的子序列数等于序列的幂集。
在你的例子中 X = {A, B} 可能的子序列是 {empty, A, B ,AB}