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; }
发表评论
沙发空缺中,还不快抢~