We value your feedback.
Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!
Course Of The Month
9 days, 9 hours left to enrollBecome a Premium Member and unlock a new, free course in leading technologies each month.
Solved
Recursion for power set
Posted on 2000-03-27
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.
[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
- Learn & ask questions
-
3
2-
2
- +2
9 Comments
#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)...
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...
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...
Yes his question was to right the code, you're just trying to scalp points with out a clue how to do this!
Featured Post
We value your feedback.
Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!
Question has a verified solution.
If you are experiencing a similar issue, please ask a related question
Preface
I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net. To view more iPhone tutorials, visit www.sdkexpert.net.
This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand
and use for-loops in the C programming language.
Suggested Courses
Earn Certification
HTML5 Specialist - Certification
Free withPremium
Course of the Month9 days, 9 hours left to enroll
623 members asked questions and received personalized solutions in the past 7 days.
Join the community of 500,000 technology professionals and ask your questions.