Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Recursion for power set

Posted on 2000-03-27
Medium Priority
1,418 Views
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.
0
Question by:sailwind
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 3
• 2
• 2
• +2

LVL 7

Expert Comment

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

LVL 18

Expert Comment

ID: 2664581
#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

LVL 3

Author Comment

ID: 2665294
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

LVL 2

Expert Comment

ID: 2669155
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

LVL 2

Expert Comment

ID: 2669161
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

LVL 2

Accepted Solution

yairy earned 300 total points
ID: 2682213
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

LVL 18

Expert Comment

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

LVL 2

Expert Comment

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

LVL 2

Expert Comment

ID: 2684397
in that case, what's wrong with my definition? :>
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see soâ€¦
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and infâ€¦
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
###### Suggested Courses
Course of the Month7 days, 12 hours left to enroll