编程中的集合运算

2017年9月13日

对于一个集合,我们想要列举它的所有子集,可以用二进制来进行枚举。1 表示取集合中的数,0 表示不取集合中的数,比如,对于集合 S = {1, 3, 4},用二进制来枚举的话是这样:
首先,我们得知道一个有n个元素的集合总共有 $$2^n$$个子集。
接下来看如何得到 S = {1, 3, 4} 的所有子集

十进制二进制子集
0000$$\varnothing$$
1001{4}
2010{3}
3011{3,4}
4100{1}
5101{1,4}
6110{1,3}
7111{1,3,4}

观察下就可以明白,用二进制表示上的哪个数是1,就取集合中的哪个数。知道了这个原理后,就可以很容易的编写代码来列举子集了。

知道了原理,接下来就是实践了。附一些位运算知识:

运算符含义功能
&按位与如果两个相应的二进制位都为1,则该位的结果值为1;否则为0。
按位或两个相应的二进制位中只要有一个为1,该位的结果值为1。
^按位异或若参加运算的两个二进制位同号则结果为0(假)异号则结果为1(真)
~取反用来对一个二进制数按位取反,即将0变1,将1变0。
<<左移左移运算符是用来将一个数的各二进制位全部左移N位,右补0。
>>右移a的各二进制位右移N位,移到右端的低位被舍弃,对无符号数,高位补0。

举例:

位运算或 “丨” or与 “&”and非 “~” not异或 “^” xor
操作数101010101110101011010101010000001
操作数20010101010101010(无)01111111
结果01111111100000000101010111111110

这些位运算符跟逻辑运算符(&&,|| , !)是有一定的相似性的,区别就在于位运算符的对象是二进制的数。对于 5 & 2 这个结果是多少呢?由于 5 跟 2 都是十进制数,把它们用二进制来表示就是 101 & 010,结果就是 0。而如果是 5 | 2的话,转成二进制 101 | 010,结果是 $$111_2$$,再转为十进制就是 7 了,就是说 5 | 2 = 7

一些集合运算就可以对应写成如下方式(以C++为例)。

集合表示方法
空集0
只含有第 i 个元素的集合{i}1 << i
含有全部 n 个元素的集合{0, 1, …, n – 1}(1 << n) – 1
判断第 i 个元素是否属于集合 Sif (S >> i & 1) 或者 if (S & 1 << i)
向集合中加入第 i 个元素 $$S \cup \{i\}$$S 丨 1 << i
从集合中去除第 i 个元素 $$S - \{i\}$$S & ~(1 << i)
集合 S 和 T 的并集 $$S\cup T$$S 丨 T
集合 S 和 T 的交集 $$S\cap T$$S & T

一份枚举子集的代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int a[] = {1, 3, 4}; //所需要枚举的集合
  int n = 3; //所枚举集合的元素个数
  for (int s = 0; s < 1 << n; s++) { //总共有 2^n 个子集
    for (int j = 0; j < n; j++) {
      if (s & 1 << j) { //判断第 j 个元素是否属于集合 s
        cout << a[j] << ' ';
      }
    }
    cout << endl;
  }
  return 0;
}

One thought on “编程中的集合运算

发表评论

电子邮件地址不会被公开。 必填项已用*标注