Solved

Recursion for power set

Posted on 2000-03-27
9
1,194 Views
Last Modified: 2008-03-10
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
Comment
Question by:sailwind
  • 3
  • 2
  • 2
  • +2
9 Comments
 
LVL 7

Expert Comment

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

Expert Comment

by:deighton
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

by:sailwind
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

by:_lychee_
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
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 
LVL 2

Expert Comment

by:_lychee_
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

by:
yairy earned 100 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

by:deighton
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

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

Expert Comment

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

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Suggested Solutions

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
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…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

708 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now