[알고리즘] Recursion의 응용 - 멱집합(power set)

Recursion의 응용 - 멱집합(power set) 

어떤집합의 모든 부분 집합의 집합을 멱집합이라고 한다.

멱집합을 계산하기에 앞서 기본적으로, 집합의 부분집합을 살펴보자

원소의 개수가 n개인 모든 가능한 부분집합의 개수는 2^n개이다.

각각의 원소에 대해서 그 원소를 포함하던가, 포함하지 않던가라는 

2개의 경우의수를 적용한다면

2x2x...xN 이므로 결국 2^n이 된다. 

그렇다면 크기가 N인 모든 부분집합의 집합을 어떤식으로 구하는 것일까

Recursion을 이용한다면 다음과 같은 조건을 세운다

{a,b,c,d,e,f} 의 모든 부분집합을 나열한다고 했을 때

1) a를 제외한 {b,c,d,e,f}의 모든 부분집합을 나열하고

2) {b,c,d,e,f}의 모든 부분 집합에 {a}를 추가한 집합을 나열한다.

2)의 조건을 좀더 자세히 살펴보자

 {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}를 추가한 집합들을 나열한다.

powerSet(s)
if S is an empty set
    print nothing;
else
    let t be the first element of S;
    find all subsets of S-{t} by calling powerSet(S-{t});                                                  
    print the subsets;
    print the subsets with adding t;

이것을 슈도 코드로 나타내면 다음과 같다.

집합 s가 들어왔을때 이 집합의 멱집합을 구해야한다. 

base case를 살펴보자

S가 공집합이라면 S를 출력, 또는 아무것도 출력하지 않는다.

어떤한 원소 t에 대해서 

t를 제거한 원소에 대한 모든 부분집합을 구하여 부분집합을 출력하고

그 부분집합들에 방금전 제외했던 t를 더해서 출력한다.

그러나 위와같은 슈도 코드에는 몇가지 문제점이 있다.

재귀적으로 부분집합들을 구한 후 한번은 그대로 출력하고 한번은 t를 더해서 출력하려면

powerset이라는 함수는 s-{t}의 모든 부분집합들을 구해서 리턴해줘야한다는 것이다.

따라서 집합을 print가 아니라 return 을 해줘야한다.

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(PU{t},S-{t})

그러므로 다음과 같은 코드로 수정이 가능하다.

입력으로 2개의 집합을 받는다.

S의 멱집합을 구한 후 각각의 집합 P를 합하여 합집합으로 출력하는 것이다.

맨처음 powerSet을 호출 할경우 P는 공집합, S는 전체집합으로 호출한다.

조금전으로 돌아가 이전에 작성한 조건을 다시 살펴보자

{b,c,d,e,f}의 모든 부분 집합에 {a}를 추가한 집합을 나열하려면

1) {c,d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고

2) {c,d,e,f}의 모든 부분집합에 {a, b}를 추가한 집합들을 나열한다

라고 했을 때 2)에서 

{c,d,e,f}가 집합 S, {a,b}가 집합 P에 해당한다.

집합 S는 k번째부터 마지막 원소들까지,

집합 P는 처음부터 k-1번째 원소들 중 일부이다.

즉, 다음과 같이 P와 S를 나타낼 수 있는 것이다.

다시 말해서 매개변수를 k라는 인덱스와 include라는 배열로 표현하겠다는 뜻이다.

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);
}
 

이를 코드화 하면 다음과 같이 표현할 수 있다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘