멱집합

1. 멱집합

주어진 집합의 모든 부분집합의 집합을 멱집합이라 한다.

예를 들어 집합 A = {a, b, c, d}일 때, 멱집합의 개수는 이다. 즉, n개의 원소에 대해 자신을 포함하는지 아닌지, 2가지 경우의 수가 있으므로 집합의 원소의 개수가 n개일 때 멱집합의 개수는 개이다.

2. Recursion을 이용한 멱집합 구하기

1) Recursion을 사용하여 멱집합을 구하는 방법은 다음과 같은 과정을 반복하면 된다.

예를 들어, {a, b, c, d, e, f}의 멱집합을 구하려면

1. a를 제외한 {b, c, d, e, f}의 멱집합을 나열하고,
2. {b, c, d, e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다.

{b, c, d, e, f}의 멱집합에 {a}를 추가한 집합들을 나열하려면

1. {c, d, e, f}의 멱집합에 {a}를 추가한 집합들을 나열하고,
2. {c, d, e, f}의 멱집합에 {a, b}를 추가한 집합들을 나열한다.

{c, d, e, f}의 멱집합에 {a}를 추가한 집합들을 나열하려면

1. {d, e, f}의 멱집합에 {a}를 추가한 집합들을 나열하고
2. {d, e, f}의 멱집합에 {a, c}를 추가한 집합들을 나열한다.

     2) Pseudo-code

S의 멱집합을 구한 후 각각에 집합 P를 합집합하여 출력

powerSet(P, S)

if S is an empty set

             print P;

else

             let t be the first element of S;

             powerSet(P, S-{t});

             powerSet(P U {t}, S-{t});

이 코드는 다음과 같이 나타낼 수 있다.

{b, c, d, e, f}의 멱집합에 {a}를 추가한 집합들을 나열하려면

1. {c, d, e, f}의 멱집합에 {a}를 추가한 집합들을 나열하고,
2. {c, d, e, f}의 멱집합에 {a, b}를 추가한 집합들을 나열한다.

• 집합 S: k번째부터 마지막 원소까지 연속된 원소
• 집합 P: 처음부터 k-1번째 원소들 중 일부

[출처: 권오흠, 영리한 프로그래밍을 위한 알고리즘 강좌]

• 집합 S는 data[k], …, data[n-1]이고, 집합 P는 include[i] = true, i=0,…,k-1인 원소들이다.
• 집합 P는 boolean을 사용하였다.

3) 소스코드

public class PowerSet {
       private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
       private static int n = data.length;
       private static boolean [] include = new boolean[n];


       public static void powerSet(int k){
             if(k==n){
                    for(int i=0; i<n; i++)
                           if(include[i])
                                 System.out.print(data[i]+" ");
                    System.out.println();
                    return;
             }
             include[k]=false;
             powerSet(k+1);
             include[k]=true;
             powerSet(k+1);
       }


       public static void main(String[] args) {
             powerSet(0);
       }
}