子集生成各算法

  1. 增量构造法,一次选出一个元素放到集合中
    • 枚举集合{0,1,2,…,n}的所有子集
      cpp
      // A表示缓存数组,cur表示已放入的数个数
      void print_subset(int n, int* A, int cur){
      for (int i = 0; i < cur; i++){
      printf("%d ", A[i]); // 打印当前集合
      }
      printf("\n");
      int s = cur ? A[cur - 1] + 1 : 0; // 确定当前元素的最小可能值
      for (int i = s; i < n; i++){
      A[cur] = i;
      print_subset(n, A, cur + 1); // 递归构造子集
      }
      }
      // 调用方法
      print_subset(n, A, 0);
    • 枚举集合数组B的所有子集
      cpp
      void print_subset(vector<int>& A, vector<int>& B, int cur) {
      for (auto num : A) {
      cout << num << ' ';
      }
      cout << endl;
      for (int i = cur; i < B.size(); i++) {
      A.push_back(B[i]);
      print_subset(A, B, i + 1);
      A.pop_back();
      }
      }
      // 调用方法
      print_subset(A, B, 0);
  2. 位向量法
    • 枚举集合数组A中的所有子集
      cpp
      // B是标记数组,表示此位上有或无
      void print_subset(vector<int>& A, vector<bool>& B) {
      if (B.size() == A.size()) {
      for (int i = 0; i < B.size(); i++) {
      if (B[i]) cout << A[i] << ' ';
      }
      cout << endl;
      return;
      }
      B.push_back(true);
      print_subset(A, B);
      B.back() = false;
      print_subset(A, B);
      B.pop_back();
      }
      // 调用方法
      vector<int> A{...}; // A是集合数组
      vector<bool> B; // B是空标志数组
      print_subset(A, B);
  3. 二进制法
    • 枚举集合A中的各元素
      cpp
      // n为标志数字,A为集合数组
      void print_subset(vector<int>& A, int n) {
      int tmp = 1; // 用tmp来解析标志数字n
      for (auto num : A) {
      if (tmp & n) cout << num << ' ';
      tmp <<= 1;
      }
      cout << endl;
      }
      // 调用方法
      for (int i = 0; i < (1 << A.size()); i++) {
      print_subset(A, i);
      }

发表评论