멱집합(Powerset)

멱집합이란?

- 집합의 모든 부분집합으로 이루어진 집합을 말한다.

- n개의 원소를 가진 집합이 멱집합을 이루는 경우의 수는 2^n이다. (각각의 원소를 포함하는가/ 안하는가)

 

- 멱집합을 만드는 예시)

{a,b,c,d,e,f}의 모든 부분집합을 나열하려면 -

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

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

              - >a를 포함하는가? 포함하지 않는가? 2가지

 

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

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

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

             ->b를 포함하는가? 포함하지 않는가? 2가지

 

---

 

그렇다면 멱집합의 코드를 구상해보자.

 

 

1. 잘못된 ver.

- S의 멱집합을 출력하는 코드

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

->하지만 이 코드에는 많은 문제점이 있다.

1) 이렇게 된다면 powerSet함수는 여러 개의 집합들을 return 해야한다.

2) 두 종류의 집합을 반환해야하기 때문에, 또 다른 집합(매개변수(?))을 추가해서 출력하도록 하기 어렵다.

3) 2^n개의 집합을 메모리에 저장하게 되는데, 굳이 그럴 필요가 없다.

 

 

2. 올바른 ver.

- 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});//t포함X
		powerSet(P + {t}, S - {t});//t포함O
	}
}

- recursion 함수가 두 개의 집합을 매개변수로 받도록 설계해야 한다는 의미이다!

- 두 번째 집합(P)의 모든 부분집합들에 첫 번째 집합(S)을 합집합하여 출력한다.

 

 

* 집합 S는 data[k]~data[n-1]이고, 집합 P는 include[i]=true, i=0~k-1인 원소들이다.

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

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

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

 

---

 

멱집합 완성된 코드

- data[k]~data[n-1]의 멱집합을 구한 후, 각각에 include[i]=true, i=0~k-1인 원소를 추가하여 출력하라.

#include <iostream>
using namespace std;
char data[] = { 'a','b','c','d','e','f' };
int n = data.length();
bool* include = new bool[n];
void powerSet(int k) {
	if (k == n) {
		for (int i = 0; i < n; i++)
			if (include[i])
				cout << data[i] << "  ";
		cout << endl;
		return;
	}
	include[k] = false;
	powerSet(k + 1);
	include[k] = true;
	powerSet(k + 1);
}

*처음 이 함수를 호출할 때엔 powerSet(0)으로 호출한다.

즉, P는 공집합이고 S는 전체집합으로 한다.

---

 

멱집합 '상태공간트리'로 알고리즘 이해해보기

*상태공간트리란?

1) 해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리이다.

2) 트리의 모든 노드들을 방문하면 해를 찾을 수 있다.

3) 루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술한다.

 

- {a,b,c}를 위의 코드처럼 구상했을 때 만들 수 있는 상태공간트리다.

- 상태공간트리로 알고리즘을 생각해보면 코드를 더 명확하게 이해할 수 있다.

 

1.

bool* include = new bool[n];
void powerSet(int k) {

-> k는 어떤 트리의 레벨에 위치하는가를 의미한다.

-> include는 그 전에 어디까지 레벨을 거쳐왔는지를 의미한다.

 

2.

	if (k == n) {

-> 현재 위치인 k가 n과 같다는 것은 내 위치가 리프노드(마지막 줄)라는 것을 뜻한다.

 

3.

	include[k] = false;
	powerSet(k + 1);
	include[k] = true;
	powerSet(k + 1);

-> 트리의 마지막 줄이 아니라면, 먼저 트리의 왼쪽으로 내려갔다가 다음에 오른쪽으로 내려가는 것을 의미한다.

 

---

신통방통 recursion 그리고 state space tree..

집합의 부분집합을 리턴하는 게 이렇게 어려울 줄이야

매개변수를 두개 써서 부분집합을 또 나누는 것은 신기한 아이디어 같다.