集合的二进制表示法

概述

有一个包含nn个不同元素的集合，假设为：{1,2,3,..,n}\{1,2,3,..,n\}，他的子集个数有2n2^n个，当nn的大小不是特别大的时候，例如n≤30n\le 30时（约等于10737418241073741824），我们则可以在合理的时间内枚举出它的所有子集。

子集的表示方法

  1. 数组表示法

  • 直接用数组表示集合，这种表示方式比较直接，c++中的任何容器类型都可以用来存储集合

  1. 01 bit串表示法（二进制表示法）

  • 使用一个整数的二进制形式来表示集合，二进制数第i个bit位为0，则表示全集中的第i个元素不在子集中，二进制数第i个bit位为1，则表示在子集中；例如一个包含3个元素的集合{1,2,3}的所有子集，可以用<8的整数来表示：
    • 0 -> 000 -> {}
    • 1 -> 001 -> {1}
    • 2 -> 010 -> {2}
    • 3 -> 011 -> {1,2}
    • 4 -> 100 -> {3}
    • 5 -> 101 -> {1,3}
    • 6 -> 110 -> {2,3}
    • 7 -> 111 -> {1,2,3}

子集的遍历

  1. 递归遍历

使用数组表示法表示集合时，子集遍历使用递归遍历实现起来会比较容易些，二进制表示法当然也可以使用递归遍历，但是二进制表示法有更简洁的遍历方法，没有必要使用递归实现

  • 设递归函数enumerate(vector s, int idx)，s中存储下标小于idx的元素中选出的子集，初始为空，当遍历到第idx个元素时，有两种选择，一种是选择第idx个元素，加入到s中，一种是不选择idx元素，则s保持不变

  • 代码实现 —— 数组表示法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void print(const vector<int>& s) {
  cout << "[";
  for (int val : s)
      cout << val << ",";
  cout << "]" << endl;
}

constexpr int N = 4;
// idx从0开始
void enumerate(vector<int> &s, int idx) {
    if (idx == N) {
        print(s);
        return;
    }
    s.emplace_back(idx);
    enumerate(s, idx + 1);
    s.pop_back();
    enumerate(s, idx + 1);
}

int main() {
  vector<int> s;
  enumerate(s, 0);
  return 0;
}

  1. 迭代遍历

  • 代码实现 —— 数组表示法

遍历过程相当于二进制表示法从2n−12^n-1遍历到00到过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void print(const vector<int>& s) {
  cout << "[";
  for (int val : s)
      cout << val << ",";
  cout << "]" << endl;
}

constexpr int N = 4;
// idx从0开始
void enumerate() {
    vector<int> s;
    int idx = 0;
    // 从全集开始遍历
    while(idx < N) {
        s.emplace_back(idx);
        idx++;
    }
    print(s);

    while(s.size() > 0) {
        // 集合前缀为s，且包含idx-1的子集已经遍历过了，则将其弹出
        if (s.back() == idx - 1) {
            s.pop_back();
            while (idx < N) { // idx-1不选，后面全选的情况开始遍历
                s.emplace_back(idx);
                idx++;
            }
            print(s);
        } else {
            // 集合前缀为s，且不包含idx-1的集合也遍历过了，该考虑前面的元素了
            while (s.back() != idx - 1) {
                idx--;
            }
        }
    }
}

int main() {
  enumerate();
  return 0;
}

  • 代码实现 —— 二进制表示法

非常简单，直接遍历所有比2N2^N小的整数即可

1
2
3
4
// O(2^N)
for (int mask = 0; mask < (1<<N); ++mask) {
    print(mask);
}

二进制表示法子集遍历的一些其他技巧

  • 遍历任意整数mask代表的集合的子集
1
2
3
4
// O(2^(mask的二进制表示中1的个数))
for (int j = mask; j >= 0; j = (j - 1) & mask) {
    print(j);
}

(j-1)&mask相当于把j的最低位1置为0，同时把该位右边所有的属于mask集合的位设置为1，所以(j-1)&mask是小于j的mask子集中最大的一个，因此这个遍历能够遍历到所有的mask子集；该实现与迭代遍历-数组表示法中的代码思路相同。

  • 遍历所有元素个数为k的子集

参考：https://www.cnblogs.com/JihuiPeng/p/13666678.html

1
2
3
4
5
6
int mask = (1 << k) - 1;
while (mask < 1 << n) {
	//进行针对组合的处理 
	int x = mask & -mask, y = mask + x;
	mask = ((mask&~y) / x >> 1) | y;
}

代码拆解：

1
2
3
4
5
6
7
8
9
10
11
// 找到字典序最小的1的位置，1100 1100 → 0000 0100
int x = mask & -mask;
// 将字典序最小的1的连续区间置为0，并将区间左侧第一个0置为1，1100 1100 → 1101 0000
int y = mask + x;
// 取出字典序最小的1的连续区间，1100 1100 → 0000 1100
int z = mask & ~y;
// 将上一步取出的区间右移，直至区间中1的个数减少一个，0000 1100 → 0000 0001
// 'z/x'相当于去掉右侧多余的0，'>>1'则使剩下的1的个数减少一个
int b = (z / x) >> 1;
// 0000 0001 | 1101 0000 → 1101 0001
mask = b | y;	  //取并集