C++实现求一集合的幂集

Power Set

集合S的幂集 P(S) 是S所有的子集. 例如 S = {a, b, c} 则它的幂集就是 P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}. 其中{}表示空集.

Algorithm:

输入: Set[], set_size
1. 获取集合的大小
    powet_set_size = pow(2, set_size)
2. 从0开始直到pow_set_size遍历集合
     (a)循环从i到set_size 
         (i) If ith bit in counter is set Print ith element from set for this subset 
     (b) Print seperator for subsets i.e., newline

Example:

Set  = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111

Value of Counter            Subset
    000                    -> Empty set
    001                    -> a
    010                    -> b
    011                    -> ab
    100                    -> c
    101                    -> ac
    110                    -> bc
    111                    -> abc

Program:

#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;
}