[JAVA] 멱집합

{a, b, c, d, e, f}의 모든 부분집합 =

(1) a를 포함하지 않는 {b, c, d, e, f}의 부분집합 + (2) a를 포함하는 {b, c, d, e, f}의 부분집합

(1)과 (2)의 크기는 사실 같습니다. 결국 (1)에서 구한 {b, c, d, e, f}의 부분집합에 a를 더한 것들이 (2)이기 때문입니다.

만약 (1)의 크기가 2^5이라면, (2)의 크기 역시 2^5입니다. 때문에 (1) + (2)는 2^5* 2 = 2^6입니다.

여기서 recursion을 발견할 수 있습니다.

 

 

{b, c, d, e, f}에 대해서도 위의 과정에서 했던 것처럼 b를 포함하지 않는 부분집합과 b를 포함하는 부분집합을 더해줍니다.

S는 매개변수로 주어지는 집합 

recursion을 통해 부분 집합들을 계속 return하면 많은 양의 데이터가 메모리의 stack영역에 저장되었다 사라지기 때문에 CPU의 사용 측면에서 효율적이지 않기 때문에 부분집합을 출력까지만 하고, return하지는 않는 구조를 사용해야 합니다.

 

그런데 하위 부분집합을 return하지 않고 출력만 하게되면, 이전 단계에서 제외한 멤버와 하위 함수를 더하는 작업이 어려워집니다.

입력으로 두 개의 집합을 받고, S의 멱집합을 구한 뒤 각각의 집합 P를 합하여 출력

S가 공집합이라면 집합 P를 출력

그렇지 않다면 t가 S의 첫 번째 원소가 되게 설정한 뒤

1) t를 제외한 S의 powerSet과

2) t를 포함한 S의 powerSet을 호출

집합 S는 원래 배열에서 k번째 부터 마지막 원소까지 연속된 집합

집합 P는 첫 번째 배열부터 k-1번째 원소들까지 연속된 집합

public class Powerset {
    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){   // 집합 P가 공집합일 때
            for(int i=0; i<n; i++){
                if(include[i])  // 배열에 i번째 문자가 존재할 때만
                    System.out.print(data[i] + " ");
            }
            System.out.println(); // println() -> 띄어쓰기
            return ;
        }
        include[k] = false; // k번째 원소를 포함하지 않는 powerSet
        powerSet(k+1);
        include[k] = true;  // k번째 원소를 포함하는 powerSet
        powerSet(k+1);
    }

    public static void main(String[] args){
        powerSet(0);	// k=0부터 시작
    }
}

---

상태공간트리: 트리의 모든 노드를 방문하면 해를 찾을 수 있는 트리. 때문에 체계적으로 모든 노드를 방문할 수 있어야 함