멱집합(powerset) 구하기

A Set is a collection (container) of certain values, without any particular order, and no repeated values. It corresponds with a finite set in mathematics. A set can be implemented as an associative array (partial mapping) in which the value of each key-value pair is ignored.

Given a set S, the power set (or powerset) of S, written P(S), or 2^S, is the set of all subsets of S.
Task : By using a library or build-in set type, or defining a set type with necessary operations, write a function with a set S as input that yields a power set 2^S of S.

For example, the power set of {1,2,3,4} is {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}.

#include <stdio.h>
#include <stdlib.h>
#define max_size 101
int powerset(int x[], int t[], int i, int n, int p);

void main()
{
 int i, n, t[max_size];
 int x[max_size];

 printf("\n\n *** Powerset! *** \n\n Node = ");
 scanf("%d",&n);

 if (n<=0 || n>=max_size) exit(0);
 printf("\n S = {");
 for (i=0; i<n;i++) {
  x[i]=i+1;
  t[i]=0;
  printf("%d",x[i]);
  if (i!=n-1) printf(", ");
 }

 printf("}\n\n { }");
 powerset(x,t,0,n-1,n-1);
}

int powerset(int x[], int t[], int i, int n, int p)
{
 int j, k;

 if (p > i) {
  powerset(x,t,i+1,n,p);
  p=i;
 }

 if (i != n) {
  for(j=t[i]; j<=i; j++) {
   t[i] = j;
   t[i+1] = t[i] + 1;
   powerset(x, t, i+1, n, p);
  }
 }
 else {
  for (j=t[i]; j<=n; j++) {
   printf("\n { ");
   for (k=p; k<n; k++) printf("%d, ",x[t[k]]);
    printf("%d }",x[j]);
  }
 }

 return 0;
}

If we have a set {a,b,c}:

• Then a subset of it could be {a} or {b}, or {a,c}, and so on,
• And {a,b,c} is also a subset of {a,b,c} (yes, that's true, but its not a "proper subset")
• And the empty set {} is also a subset of {a,b,c}

In fact, if you list all the subsets of S={a,b,c} you will have the Power Set of {a,b,c}:

P(S) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

Think of it as all the different ways you can select the items (the order of the items doesn't matter), including selecting none, or all.

How Many Subsets

Easy! If the original set has n members, then the Power Set will have 2ⁿ members

Example: in the {a,b,c} example above, there are three members (a,b and c of course).

So, the Power Set should have 2³ = 8, which it does!

Notation

The number of members of a set is often written as |S|, so we can write:

|P(S)| = 2ⁿ

Example: for the set S={1,2,3,4,5} how many members will the power set have?

Well, S has 5 members, so:

|P(S)| = 2ⁿ = 2⁵ = 32

You will see in a minute why the number of members is a power of 2

It's Binary!

And here is the most amazing thing. If you want to create the Power Set, just write down the sequence of binary numbers (using n digits), and then let "1" mean "put the matching member into this subset" OK, it is easier to show with an example:

	abc	Subset
0	000	{ }
1	001	{c}
2	010	{b}
3	011	{b,c}
4	100	{a}
5	101	{a,c}
6	110	{a,b}
7	111	{a,b,c}

Well, they are not in a pretty order, but they are all there.