Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1518
  • Last Modified:

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.
0
sailwind
Asked:
sailwind
  • 3
  • 2
  • 2
  • +2
1 Solution
 
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
 
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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
_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
 
yairyCommented:
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
 
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

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

  • 3
  • 2
  • 2
  • +2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now