In this FREE six-day email course, you'll learn from Janis Griffin, Database Performance Evangelist. She'll teach 12 steps that you can use to optimize your queries as much as possible and see measurable results in your work. Get started today!

Hi there,

I'm trying to derive a recursive function that will print out the elements of a power set A. Power set is basically defined as:

Set A = {1, 2, 3)

P(A) = {{0}, {1}, {2}, {3}, {1,2}, {1, 3}, {2,3}, {1,2,3}}

Furthermore, if

Set A = {{1,2,3}, {4,5}, 6}

P(A) = {{0}, {{1,2,3}}, {{4,5}}, {6}, {{1,2,3}, {4,5}}, {{1,2,3}, 6}, {{4,5}, 6}, {{1,2,3}, {4,5}, 6}}

If someone can help me formulate a recursive function that will take in the set, then print out the power set elements, it would be much appreciated. Thanks.

I'm trying to derive a recursive function that will print out the elements of a power set A. Power set is basically defined as:

Set A = {1, 2, 3)

P(A) = {{0}, {1}, {2}, {3}, {1,2}, {1, 3}, {2,3}, {1,2,3}}

Furthermore, if

Set A = {{1,2,3}, {4,5}, 6}

P(A) = {{0}, {{1,2,3}}, {{4,5}}, {6}, {{1,2,3}, {4,5}}, {{1,2,3}, 6}, {{4,5}, 6}, {{1,2,3}, {4,5}, 6}}

If someone can help me formulate a recursive function that will take in the set, then print out the power set elements, it would be much appreciated. Thanks.

#include<string.h>

main()

{

int n,c,ic,zz=0,d;

char **elements,x[80],comma[2];

int *flags;

comma[0]=0;

comma[1]=0;

printf("\nNumber of elements ");

scanf("%i",&n);

elements = (char **) malloc(n * sizeof(char **));

for (c=0;c<n;c++)

{

printf("\nElement no %i = ",c+1);

scanf("%s",x);

elements[c] = (char *) malloc((strlen(x) + 1) * sizeof(char *));

strcpy(elements[c],x);

}

flags = (int *) malloc(n * sizeof(int));

for (c = 0;c<n;c++)

flags[c]=0;

printf("{0}");

do{

ic = 1;

for(c=0;c<n;c++)

{

flags[c]+=ic;

ic^=ic;

if(flags[c]==2)

{

ic=1;

flags[c]^=flags[c];

}

}

if (ic==0){

printf("\n{");

d=0;

for(c=0;c<n;c++)

{

comma[0]=0;

if (d>0) comma[0]=',';

if (flags[c])

{

printf("%s%s",comma,elemen

d++;

}

}

puts("}");

}

else

{

zz=1;

}

}

while(zz==0);

for (c = 0;c<n;c++)

{

free(elements[c]);

}

free(elements);

free(flags);

getch();

}

anywayz, if u enumerate the elements in the original set A, as a1, a2, ..., an, then

P(A) is the union of:

{}, {a1} U P(A1), {a2} U P(A2), {a3} U P(A3), ..., {an}

where Ai is the union of aj, where j > i.

that's a recursive definition of the power set i think...

when i say {a1} U P(A1) i mean u add a1 to all the sets in P(A1)...

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

Iterative:

lets look at a binaric number with 3 digits:

000

001

010

..

..

111

lets say that every digit represents

if an Item appears or not in the group.

Actualy we got all the sub-sets....

Recursive:

R(n)

for n items,

the groups are R(n-1) items + the n'th item with the group and without the group.

If a |group|=1, then its only

with and without the item in the group.

Any questions...