본문

[2017.12.27] 25. Recursion와 멱집합(PowerSet)

도입

이번 포스팅에서는 지난 포스팅 배웠던 Recursion을 이용해 집합의 멱집합(PowerSet)를 구하는 방법을 실습할 예정이다.



멱집합(PowerSet)의 개념

멱집합(PowerSet)은 대상집합의 모든 부분 집합이다. 예를 들어, 

대상 집합: {1,2,3}

멱집합 : 공집합, ,{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

이다.



실습

Step1. 멱집합(PowerSet)을 구하기 위한 Thinking

Recursion을 사용하므로 공통된 작은 문제로 생각하면


첫 번째 원소 포함   (O)     + 첫 번째 원소를 제외한 나머지의 모든 부분집합

첫 번째 원소 미포함(X)     + 첫 번째 원소를 제외한 나머지의 모든 부분집합


그래서 인자로서 True/False를 입력 받아 해당 원소의 포함 여부를 결정하려 했다.

1
2
3
4
5
6
7
if (isInclude) {
    System.out.print(data[start]);
}
 
// 재귀  
myPowerSet(start+1, end, data, true);
myPowerSet(start+1, end, data, false);
cs

그러나, 문제는 포함/미포함 되는 원소가 한번밖에 출력되지 않는다는 문제점이 있다.

그리고 근본적으로 중복으로 출력해야하는 값이 존재하는데 원소를 한개씩 출력해 처리할 수 있을까라는 생각이 들었다.



해결책

Step1. 원소의 포함 여부를 알 수 있는 boolean 배열 선언

1
private static boolean[] include = new boolean[n];
cs


Step2. boolean 배열에 따라 출력 결정 

1
2
3
4
5
6
7
8
9
10
if (depth == n) {        
    for (int i=0; i<n; i=i+1) {
        // 포함 여부에 따라 출력 
        if (include[i])
            System.out.print(data[i]);
 
        System.out.println();
        return;
    }
}
cs



결과

코드

스크린 샷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void powerSet(int depth) {
    // End Condition
    if (depth == n) {
        for (int i=0; i<n; i=i+1) {
            // 포함 여부에 따라 출력 
            if (include[i])
                System.out.print(data[i]);
        }
            
        System.out.println();
        return;
    }
    else {
        include[depth] = true;
        powerSet(depth+1);
        include[depth] = false;
        powerSet(depth+1);
    }
}
cs




#Recursion #멱집합 #java

공유

댓글 0