[알고리즘] 멱집합

유튜브의 권오흠 교수님 강의를 참고했습니다.

멱집합이란 어떤 집합의 모든 부분 집합의 집합이다.

 

우선 부분집합이 뭔지 생각해보자. data = {a,b,c,d} 라는 집합이 있을 때, 이 집합의 모든 부분집합의 개수는? 16개이다. n개의 원소를 가진 집합의 부분집합의 개수는 2^n개이다.

 

예를 들어 {a,b,c,d}의 모든 부분집합을 나열하려면

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

위 두가지 작업이 이루어지면 된다.

 

즉, {a,b,c,d}의 부분집합은 아래의 두 집단으로 구성된다.

• {a}를 포함한 집합 ⇒ 2^3개
• {a}를 포함하지 않는 집합 ⇒ 2^3개
• => 둘이 합하면 2^4개!

이걸 계속 진행한다면 아래와 같이 반복되는 모습을 볼 수 있다.

• {a, b, c, d}의 모든 부분집합들을 나열하려면
  • {b,c,d}의 모든 부분집합들을 나열하기.
  • {b,c,d}의 모든 부분집합들에 {a}를 추가한 부분집합들을 나열하기.
    • {b,c,d}의 모든 부분 집합들에 {a}를 추가한 집합을 나열하려면
      • {c,d}의 모든 부분 집합들에 {a}를 추가한 집합들을 나열하기.
        • {c,d}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하려면
          • {d}의 모든 부분집합들에 {a}를 추가한 부분집합들을 나열하기.
          • {d}의 모든 부분집합들에 {a,c}를 추가한 부분집합들을 나열하기.
      • {c,d}의 모든 부분 집합들에 {a,b}를 추가한 집합들을 나열한다.

이것을 수도코드로 나타내면 아래와 같다.

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}
		return all of them; 

이렇게 표현할 수도 있다.

PowerSet(P, s): //S의 멱집합을 구한 후 각각에 집합 P를 합하여 출력
	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})

 

아래는 C++로 구현해본 간단하게 알고리즘이다.

#include <iostream>
#include <string>

using namespace std;

int n;
string myData = "abcdef";
bool include[6];

void funPowerSet(int k) {
    if (k == n) {
        for (int i = 0; i < n; i++) {
            if (include[i]) cout << myData[i] << " ";
        }
        cout << endl;
        return;
    }
    // 포함하지 않는 부분
    include[k] = false;
    funPowerSet(k + 1);

    // 포함하는 부분
    include[k] = true;
    funPowerSet(k + 1);
}

int main() {
    n = myData.size();
    funPowerSet(0);
}