재귀(recursion) 5

멱집합(Powerset)

• 임의의 집합 data의 모든 부분집합을 출력하라.
• 모든 가능한 갯수 찾기 문제

예시

data = {a, b, c, d}

• 2개의 경우의 수 (true or false);
• 2^4 = 16개의 가능한 부분집합.

Recursive Thinking

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

즉 위 집합의 부분집합들은 a를 포함한 집합과 그렇지 않은 집합으로 나뉜다. 그렇지 않은 집합을 나열하고, 거기에 a를 추가한 집합을 나열해 주면 모든 부분집합을 나열할 수 있다.

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

조금 더 나가면?

• {c,d,e,f}의 모든 부분집합에 {a} 를 포함한 부분집합을 나열하고
• {c,d,e,f}의 모든 부분집합에 {a, b}를 추가한 집합들을 나열한다.

Mission: S의 멱집합을 출력해라

pseudo code:

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;

이렇게 하려면 powerset 함수는 여러 개의 집합들을 return 해야 한다.

즉 S가 N이라면 내부의 powerset은 2^N-1 의 부분집합을 리턴해 주어야 하는 것이다.

하지만 위의 코드에서는, 부분집합 내의 부분집합을 리턴해주지 않으므로 S-{t}의 부분집합을 구할 수 없다.

어떻게 해야 할까?

미션을 다시 설정해 다음과 같이 다시 짤 수 있다.

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

Recursion 함수가 두 개의 집합을 매개변수로 받도록 설계해야 한다는 의미이다. 두 번째 집합의 모든 부분집합들에 첫번째 집합을 합집합하여 출력한다.

powerSet(P, S)
	if S is an empty set
		print P;
	else
		let t be the first elem of S;
		powerSet(P, S-{t}) // t를 포함하지 않는 부분집합
		powerSet(P U {t}, S-{t}) // t를 반드시 포함하는 부분집합

이는 다음과 같다

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

여기서 {c,d,e,f} 집합이 S집합이 되고, {a,b} 집합이 P집합이 된다.

집합 S는 k번째 인덱스부터 나머지 전체까지의 집합이다. 즉 k번째 인덱스를 알 수 있으면 집합 S를 알 수 있다.

집합 P는 반대로 처음부터 k-1번째 원소들 중 일부이다. (위의 예시의 경우, {a}혹은 {a,b} 가 될 수 있다.)

여기서, 다음과 같이 p의 원소들의 포함 여부를 결정하는boolean 배열을 만들어 P를 나타낼 수 있다.

char[] data = {a,b,c,d,e,f,g,h,i,j,k,l}
boolean[] include = {true, false, true, true, false, false, ...}

char[] P = {a,c,d}

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

그러면 실제 코드를 보자.

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

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

처음 이 함수를 호출할 때는 powerSet(0)으로 호출한다. 즉 P는 공집합이고 S는 전체집합이다.

base case는 집합 S가 공집합일 때, 즉 k가 n이 될 때이다.

그 다음 data[k]를 포함하지 않는 경우, 포함하는 경우 모두 재귀를 돌리면 된다.

다른 접근법

저번 시간에 배운 상태공간트리로 이 문제를 풀 수 있다.

즉 루트에서 출발해 트리의 모든 노드들을 방문함으로써 해를 찾는 과정. DFS.

이러한 접근법으로 다시 위의 코드를 보자.

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

• include와 k는 트리상에서 현재 나의 위치를 표현한다.
• k가 n이라는것은 현재 레벨이 리프 노드에 있다는 것을 의미한다. 마지막 레벨에서는 더 이상 탐색할 필요가 없으므로 리턴한다.
• include[k]가 true, false일 때 모두 탐색한다는 것은, 모든 노드를 다 탐색한다는 것을 의미한다.

출처: 권오흠 교수님 알고리즘 강좌