Administration of Active Directory does not have to be hard. Too often what should be a simple task is made more difficult than it needs to be.The solution? Hyena from SystemTools Software. With ease-of-use as well as powerful importing and bulk updating capabilities.
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.
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.
Asked:
Who is Participating?
#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,elemen
d++;
}
}
puts("}");
}
else
{
zz=1;
}
}
while(zz==0);
for (c = 0;c<n;c++)
{
free(elements[c]);
}
free(elements);
free(flags);
getch();
}
#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();
}
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....
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...
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...
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)...
when i say {a1} U P(A1) i mean u add a1 to all the sets in P(A1)...
Yes his question was to right the code, you're just trying to scalp points with out a clue how to do this!
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...