关于使用数组和位向量的集合

文斯基

我正在以下位置阅读有关数组和位向量集的信息。

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是集合的成员。

我对以上文字的问题是

  1. 作者所说的“ 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. 作者以及为什么提出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^33个元素的集合的子集。所以这是作者提出的,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] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

如何使用postgresql使用数组和集合?

来自分类Dev

使用Cilk数组符号和STL向量

来自分类Dev

C ++数组和向量

来自分类Dev

Groovy的数组和集合

来自分类Dev

在方案中使用位向量

来自分类Dev

在方案中使用位向量

来自分类Dev

向向量和集合添加值

来自分类Dev

避免从集合和向量中进行迭代

来自分类Dev

从字符数组生成所有可能的元素组合 - 使用集合框架(列表和集合)

来自分类Dev

尝试归纳使用typedef,布尔列表和nat长度的位向量

来自分类Dev

数组和向量之间的区别

来自分类Dev

数组和集合之间的区别

来自分类Dev

使用集合交集的意外向量行为

来自分类Dev

在C ++中使用向量数组的向量

来自分类Dev

使用向量的向量的多个数组

来自分类Dev

使用数组 Json 获取关于数组的数据

来自分类Dev

使用位集访问向量索引

来自分类Dev

使用位集访问向量索引

来自分类Dev

关于Java中的集合,枚举和迭代器的困惑

来自分类Dev

关于scala中可变和不可变集合的困惑

来自分类Dev

关于scala中可变和不可变集合的困惑

来自分类Dev

使用 RDF,请求关于如何对集合的一个与 ORed(所有)成员和一个集合的 ANDed(所有)成员进行建模的建议

来自分类Dev

使用按位逻辑运算实现位向量

来自分类Dev

Bash:关于循环,数组和变量

来自分类Dev

关于数组和指针的混合声明

来自分类Dev

关于“使用严格”和$ this的范围

来自分类Dev

关于将Sentinel与Laravel和$ fillable数组一起使用的查询

来自分类Dev

关于使用malloc和char数组指针的c中的分段错误

来自分类Dev

生成没有重复列的位向量数组