PowerSet

강의 사이트

• http://www.kocw.net/home/search/kemView.do?kemId=1148815

멱집합 (PowerSet)

• 멱집합은 주어진 집합의 모든 부분 집합을 말한다.

1단계

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

3단계

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

pseudo code

• 최초 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해야 한다. 어떻게 해야 하나?

• 수정 후 pseudo code

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

• S의 멱집합을 구한 후 각각에 집합 P를 합집하여 출력하라
• recursion 함수가 두 개의 집합을 매개변수로 받도록 설계해야 한다는 의미.
• 두 번째 집합의 모든 부분집합들에 첫 번째 집합을 합집합하여 출력한다.

public class powerset {
	
	static String[] set = new String[] {"a", "b", "c"};
	static int n = set.length;
	static boolean[] include = new boolean[n];

	private static void powerSet (int k) {
		if(k == n) {
			for(int i = 0; i < n; i++) {
				if(include[i]) {
					System.out.print(set[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);
	}
}

/*-----------------------------------------------------*/
//출력 값
	// 공집합
c 
b 
b c 
a 
a c 
a b 
a b c 

상태 공간 트리

• include과 exclude가 바뀌어 있음