c - 如何获取集合的所有可能的子集

Question

有人可以向我解释如何使用复杂度低于或等于以下的算法生成集合的所有子集吗？

#include <stdio.h>
#include <math.h>

void printPowerSet(char *set, int set_size)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;

    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
      for(j = 0; j < set_size; j++)
       {
          /* Check if jth bit in the counter is set
             If set then pront jth element from set */
          if(counter & (1<<j))
            printf("%c", set[j]);
       }
       printf("\n");
    }
}

/*Driver program to test printPowerSet*/
int main()
{
    char set[] = {'a','b','c'};
    printPowerSet(set, 3);

    getchar();
    return 0;
}

例如，如果我的输入是

3
2 3 4 

我的输出应该是

{2} {3} {4} {2,3} {2,4} {3,4} {2,3,4}

Answer 1

免责声明:以下内容旨在展示生成集合的幂集的概念。

• 从空集开始并将其添加到幂集sets:
• 对于集合 el 中的每个元素 el[i]
  • 对于集合中已存在的每个子集添加
    • 通过 Push_back el[i] 来增强 add
    • 将增强集推送到集

这是用 c++ 进行的概念证明

void generateSubset(vector<int>& el) {
    vector<vector<int>> sets;
    sets.push_back(vector<int>());
    for (int i = 0; i < el.size() ; i++) {
        vector<vector<int>> ssets;
        for (int j = 0 ; j < sets.size() ; j++ ) {
            vector<int> add(sets[j]);
            add.push_back(el[i]);
            ssets.push_back(add);
        }
        sets.insert(sets.end(), begin(ssets), end(ssets));
    }
    
//print the subsets
    for (int j = 0 ; j < sets.size() ; j++ ) {
        auto v = sets[j];
        for (auto a : v) {
            cout << a << " ";
        }
        cout << endl;
    }
    cout << "#subsets "<<sets.size() << endl;
}



int main() {
    vector<int> a = {1, 2, 3};
    generateSubset(a);
}

希望这有助于理解如何生成幂集。