• C

# Recursion for power set

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.
LVL 3
###### Who is Participating?

Commented:
here are two ways to think about it:

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...

0

Commented:
Do you already have a 'mathematical' or other formal definition of this 'function'?
0

progCommented:
#include<stdio.h>
#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,elements[c]);
d++;
}
}
puts("}");
}
else
{
zz=1;
}
}
while(zz==0);

for (c = 0;c<n;c++)
{
free(elements[c]);
}
free(elements);
free(flags);
getch();

}
0

Author Commented:
Your proposed answer works, but I'm looking for a simpler, recursive method. Do you have another suggestion? And no, I don't already have a mathematical algorithm for this....
0

Commented:
well... the empty set {} should be in the power set i think....

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...
0

Commented:
oops... that isn't very clear actually...

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

progCommented:
Yes his question was to right the code, you're just trying to scalp points with out a clue how to do this!
0

Commented:
Is my recursive definition anot accurate ?
why not leave for him to do some of the work ?
0

Commented:
in that case, what's wrong with my definition? :>
0
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.