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
sailwindAsked:
Who is Participating?
 
yairyConnect With a Mentor 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
 
KangaRooCommented:
Do you already have a 'mathematical' or other formal definition of this 'function'?
0
 
deightonCommented:
#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
The IT Degree for Career Advancement

Earn your B.S. in Network Operations and Security and become a network and IT security expert. This WGU degree program curriculum was designed with tech-savvy, self-motivated students in mind – allowing you to use your technical expertise, to address real-world business problems.

 
sailwindAuthor 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
 
_lychee_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
 
_lychee_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
 
deightonCommented:
Yes his question was to right the code, you're just trying to scalp points with out a clue how to do this!
0
 
yairyCommented:
Is my recursive definition anot accurate ?
why not leave for him to do some of the work ?
0
 
_lychee_Commented:
in that case, what's wrong with my definition? :>
0
All Courses

From novice to tech pro — start learning today.