我正在以下位置阅读有关数组和位向量集的信息。
http://www.brpreiss.com/books/opus4/html/page390.html
在本节中,我们考虑有限宇宙上的有限集。具体来说,对于一些固定且相对较小的N值,我们考虑的宇宙为{0,1,...,N-1},即从零到N-1范围内的整数集。
令U = 0,1,...,N-1}为宇宙。我们希望表示的每个集合都是U的子集。U的所有子集的集合称为U的幂集,并写为2 ^ U(即2等于U的幂)。因此,我们希望表示的集合是2 ^ U的元素。集合U中写为| U |的元素数为N。类似地,| 2 ^ U | = 2 ^ | U | = 2 ^ N。这种观察应该是显而易见的:对于通用集U的每个元素,只有两种可能性:它是给定集合的一个或不是给定集合的成员。
这暗示了2 ^ U元素的相对直接表示-布尔值的数组,一个用于通用集的每个元素。通过在U中使用数组下标,我们可以隐式表示集合。即,如果第i个数组元素为true,则i是集合的成员。
我对以上文字的问题是
作者所说的“ U的所有子集的集合称为U的幂集,写为2 ^ U(即2等于U的幂)?”例如,如果我们有U = {0,1,2}那么我们有2 ^ 3 = 8个所有子集的集合,但是我们有8个以上的集合,例如{空集},{0},{1},{2},{0,1},{0,2 },{0,3},{1,2}和{1,2,3}(即9)。如果我错了,请指正。
作者以及为什么提出2的幂而不是3等的其他数字?
请说清楚。
@haccks对于第一个问题给出的答案是正确的,但是我认为理解第二个问题实际上更为重要,因为它确切地显示了数组的真正含义。
您将集合表示{0,1,2}
为位数组,如下所示:
2 1 0 <-- set members
0 0 0 <-- bit array value (present/not present)
(出于某种原因,我已将集合向后排序,这很快就会变得很明显。)
位数组[0,0,0]
表示空集合。集合成员均不存在。该子集{1,2}
表示为:
2 1 0 <-- set members
1 1 0 <-- bit array value
每个集合成员可以存在或不存在;零或一。每个成员有两种可能性,这意味着我们具有2*2*2=2^3
3个元素的集合的子集。所以这是作者提出的,2
而不是其他一些。
现在您应该可以看到,位数组不过是带有|U|
位的二进制数。实际上,生成功率集的一种方法是从0
到进行二进制计数(2^|U|)-1
:
0 000 {}
1 001 {0}
2 010 {1}
3 011 {0,1}
4 100 {2}
5 101 {0,2}
6 110 {1,2}
7 111 {0,1,2}
现在还应该明显地知道,我已经将集合向后排序,以便第一个元素与对应于位数组的二进制数的LSB对齐。您可以用另一种方式订购它,但是bit 0
对应于似乎更合逻辑U[0]
。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句