멱집합 Powerset 알고리즘 (재귀함수 응용) with JAVA

  어떻게 생각하면 지난 N-Queens 알고리즘이 좀 더 어렵다고 생각할 수도 있겠지만, 이번 멱집합도 만만치는 않은 것 같다. 일단 수학 공부를 손에서 뗀 지 꽤 지난 시점이다 보니 수학적인 이해를 동반해야 하고, 거기에 가장 난감한 재귀함수적인 사고로 재귀함수적인 알고리즘을 짜내야 하기 때문에 복합적으로 작용이 되어 난도가 많이 올라간 것 같다는 느낌이 든다. 그렇지만 최대한 정리해보고자 한다.

 

멱집합?

Powerset

---

집합 A={a, b, c, d}가 있다.

집합 A가 구성할 수 있는 부분집합의 수는 2^4=16개이다.

{Ø} => 1개

{a}, {b}, {c}, {d} => 4개

{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d} => 6개

{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d} => 4개

{a, b, c, d} => 1개

 

• 그런데 여기서 {a, b, c, d}에서 모든 부분집합을 나열하기 위해서는
  1. a를 제외한 {b, c, d}의 모든 부분집합을 나열하고 (2^3=8개)
     • { } => 1개
     • {b}, {c}, {d} => 3개
     • {b, c}, {b, d}, {c, d} => 3개
     • {b, c, d} => 1개 
  2. {b, c, d}의 모든 부분집합에 {a}를 추가한 집합을 나열한다. (2^3=8개)
     • {a} => 1개
     • {a, b}, {a, c}, {a, d} => 3개
     • {a, b, c}, {a, b, d}, {a, c, d} => 3개
     • {a, b, c, d} => 1개
  3. 1번과 2번에서 나온 개수를 합하면 16개가 된다. 따라서 {a, b, c, d}의 부분집합의 개수는 16개이다.

위와 같이도 식이 도출될 수 있다.

이러한 성질을 이용하고 또 재귀적인 부분을 찾아 재귀함수를 직접 구현해보도록 하겠다.

 

문제 확인

---

집합 A={a,b,c,d}가 있다. 부분집합을 모두 출력하시오. 

 

• {a, b, c, d}에서 모든 부분집합을 나열하기 위해서
  • a를 제외한 {b, c, d}의 모든 부분집합을 나열하고 (2^3=8개)
    • b를 제외한 {c, d}의 모든 부분집합을 나열하고 (2^2=4개)
      • c를 제외한 {d}의 모든 부분집합을 나열하고 (2^1=2개)
        • d를 제외한 {}의 모든 부분집합을 나열하고 (2^0=1개)
        • {}의 부분 집합에 {d}를 추가한 집합을 나열한다. (2^0=1개)
      • {d}의 모든 부분 집합에 {c}를 추가한 집합을 나열한다. (2^1=2개)
    • {c, d}의 모든 부분 집합에 {b}를 추가한 집합을 나열한다 (2^2=4개)
  • {b, c, d}의 모든 부분 집합에 {a}를 추가한 집합을 나열한다. (2^3=8개)

재귀의 성질을 이용하면 위와 같이 구현을 할 수 있는 것이다.

public class PowerSet {
	private static char data[]= {'a','b','c','d'};
	private static int n=data.length;
	private static boolean[] include = new boolean[n];
	
	public static void powerSet(int k) {
		System.out.format("powerSet(%d) 호출됨.\n",k);
		if(n==k) {
			for(int i=0;i<n;i++) {
				if(include[i]) System.out.print(data[i]+" ");
			}
			System.out.println();
			return;
		}
		System.out.format("집합 %c 원소는 미포함한 부분집합 구하기 powerSet(%d)\n", data[k], k+1);
		include[k]=false;
		powerSet(k+1);
		System.out.format("집합 %c 원소를 포함시킨 부분집합 구하기 powerSet(%d)\n", data[k],k+1);
		include[k]=true;
		powerSet(k+1);
		
	}
	
	public static void printArray() {
		for(char c: data) {
			System.out.format("%c ",c);
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		powerSet(0);
	}

}

 

 

결과 화면

powerSet(0) 호출됨.
집합 a 원소는 미포함한 부분집합 구하기 powerSet(1)
powerSet(1) 호출됨.
집합 b 원소는 미포함한 부분집합 구하기 powerSet(2)
powerSet(2) 호출됨.
집합 c 원소는 미포함한 부분집합 구하기 powerSet(3)
powerSet(3) 호출됨.
집합 d 원소는 미포함한 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.

집합 d 원소를 포함시킨 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
d 
집합 c 원소를 포함시킨 부분집합 구하기 powerSet(3)
powerSet(3) 호출됨.
집합 d 원소는 미포함한 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
c 
집합 d 원소를 포함시킨 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
c d 
집합 b 원소를 포함시킨 부분집합 구하기 powerSet(2)
powerSet(2) 호출됨.
집합 c 원소는 미포함한 부분집합 구하기 powerSet(3)
powerSet(3) 호출됨.
집합 d 원소는 미포함한 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
b 
집합 d 원소를 포함시킨 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
b d 
집합 c 원소를 포함시킨 부분집합 구하기 powerSet(3)
powerSet(3) 호출됨.
집합 d 원소는 미포함한 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
b c 
집합 d 원소를 포함시킨 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
b c d 
집합 a 원소를 포함시킨 부분집합 구하기 powerSet(1)
powerSet(1) 호출됨.
집합 b 원소는 미포함한 부분집합 구하기 powerSet(2)
powerSet(2) 호출됨.
집합 c 원소는 미포함한 부분집합 구하기 powerSet(3)
powerSet(3) 호출됨.
집합 d 원소는 미포함한 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
a 
집합 d 원소를 포함시킨 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
a d 
집합 c 원소를 포함시킨 부분집합 구하기 powerSet(3)
powerSet(3) 호출됨.
집합 d 원소는 미포함한 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
a c 
집합 d 원소를 포함시킨 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
a c d 
집합 b 원소를 포함시킨 부분집합 구하기 powerSet(2)
powerSet(2) 호출됨.
집합 c 원소는 미포함한 부분집합 구하기 powerSet(3)
powerSet(3) 호출됨.
집합 d 원소는 미포함한 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
a b 
집합 d 원소를 포함시킨 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
a b d 
집합 c 원소를 포함시킨 부분집합 구하기 powerSet(3)
powerSet(3) 호출됨.
집합 d 원소는 미포함한 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
a b c 
집합 d 원소를 포함시킨 부분집합 구하기 powerSet(4)
powerSet(4) 호출됨.
a b c d