Java 재귀함수 멱집합(power set) 구하기

재귀함수 멱집합

멱집합(power set)이란,

집합론에서 멱집합은 어떤 집합 A에 대하여 A의 모든 집합들로 이루어진 집합을 A의 멱집합이라고 합니다.

(공집합과 A 집합 자체도 포함합니다.)

 

A={a, b, c, d}라는 집합 A가 있을 때, 집합 A가 구성할 수 있는 부분집합의 수는 2^4=16개입니다.

{Ø}

{a}, {b}, {c}, {d}

{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}

{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}

{a, b, c, d}

 

 

조금 다른 관점에서 보면 {a, b, c, d}의 모든 부분집합을 나열하기 위해서는

1. a를 제외한 {b, c, d}의 모든 부분집합을 나열한 것과 (2^3=8개)
   {Ø}
   {b}, {c}, {d}
   {b, c}, {b, d}, {c, d}
   {b, c, d}
   
   
2. {b, c, d}의 모든 부분집합을 나열한 것에 {a}를 추가한 집합을 나열한 것 (2^3=8개)
   {a}
   {a, b}, {a, c}, {a, d}
   {a, b, c}, {a, b, d}, {a, c, d}
   {a, b, c, d}

이 두 가지를 더한 것이 될 수 있는데요. (2^4=16개)

 

여기서 재귀의 관점으로 한 단계 더 들어가서 생각해보면

'2. {b, c, d}의 모든 부분집합을 나열한 것에 {a}를 추가한 집합을 나열한 것'에서 {b, c, d}의 모든 부분집합은 {b, c, d}에서 b를 제외한 부분집합과 b를 포함하는 부분집합으로 나누어서 생각할 수 있습니다.

1. b를 제외한 {c, d}의 모든 부분집합에 {a}를 추가한 집합을 나열한 것 (2^2=4개)
2. b를 포함한 {c, d}의 모든 부분집합에 {a}를 추가한 집합을 나열한 것 (2^2=4개)

두 가지를 더한 것으로 볼 수 있습니다. (2^3=8개)

 

 

---

 

 

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) {
    if(n==k) {
        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() 메서드를 본다면 다음과 같습니다.

코드만 봤을 때는 이해가 어려울 수 있기 때문에 아래 상태 공간 트리(State Space Tree) 이미지를 참고하여 이해를 도울 수 있습니다.

 

 

 

*** 상태 공간 트리란, 

트리의 모든 노드를 방문하면 해를 찾을 수 있는 트리입니다. 때문에 체계적으로 모든 노드를 방문할 수 있어야 합니다.

 

트리에서 최상위 노드를 루트 노드(root node, 뿌리 노드)라고 합니다. 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 하며, 자식 노드가 없는 노드를 잎 노드(leaf node, 리프 노드)라고 합니다.

 

 

 

 

상태 공간 트리

상태 공간 트리를 참고해서 위 메서드를 다시 이해해보면,

(private static char data []= {'a', 'b', 'c'}; 로 가정하겠습니다.)

 

먼저 k=0일 경우에 n은 3이기 때문에 k!=n으로 if문 내의 로직은 수행되지 않습니다.

 

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

그리고 아래 로직에서 boolean [] 배열인 include의 역할에 주목해야 하는데요.

 

// exclude a 왼쪽 노드
include[0]=false;     // k=0
powerSet(1);          // k+1=1;

// include a 오른쪽 노드
include[0]=true;     // k=0
powerSet(1);          // k+1=1;

 

include [0]=false;라는 것은 최종 리프 노드에서 결과를 출력할 때 사용될 boolean 배열 include에서 원본 배열 A의 첫 번째 값인 {a}를 포함하지 않는다고 체크한 것입니다.

그러니까 맨 위에 k=0인 루트 노드에서 exclude a인 왼쪽 노드를 타고 내려가는 것을 말합니다.

 

그리고 powerSet(1)이 실행되는데 powerSet(1)이 실행되면 어떻게 될까요?

 

// exclude b 왼쪽 노드
include[1]=false;     // k=1
powerSet(2);          // k+1=2;

// include b 오른쪽 노드
include[1]=true;     // k=1
powerSet(2);          // k+1=2;

( k=0에서 첫 번째 powerSet(1)이 실행되었을 때, 아래 powerSet(1) 메서드가 실행되기 전 위 powerSet(2) 메서드가 먼저 실행됩니다.)

 

코드를 이어서 따라가 보면 위에서 include [0]=false; 즉, a를 포함하지 않는 상태에서 include[1]=false; b도 포함하지 않게 됩니다.

그리고 powerSet(2) 메서드가 실행되고

 

// exclude c 왼쪽 노드
include[2]=false;     // k=2
powerSet(3);          // k+1=3;

// include c 오른쪽 노드
include[2]=true;     // k=2
powerSet(3);          // k+1=3;

include[2]=false; c도 포함하지 않은 include [] = {false, false, false} 상태에서 powerSet(3) 메서드가 실행됩니다.

이때는 k==n으로 if문이 실행되고, for문을 통해 boolean 배열 include를 확인하여 값이 true인 경우 한 라인에 출력합니다.

(true인 경우가 없기 때문에 Ø 공집합이 됩니다.)

 

그리고 이어서 include[2]=true; c를 포함하는 include [] = {false, false, true} 상태에서 powerSet(3) 메서드가 실행되고, 'c'가 출력됩니다.

 

 

 

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) {
    // k는 트리상에서 현재 위치를 표현합니다.
    if(n==k) {  // 현재 위치가 리드 노프이면 include를 출력합니다.
        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(P, S)
    if S is an empty set
        print P;
    else
        let t be the first element of S
        powerSet(P, S-{t});
        powerSet(p 합집합 {t}, S-{t});

역순서로 설계 부분을 한번 살펴본다면,

 

여기서 집합 S는 data[k], ..., data[n-1] 즉, k 번째부터 마지막 원소까지 연속된 원소들이고, 집합 P는 include[i]=true, i=0, ..., k-1 인 원소들 즉, 처음부터 k-1까지의 원소들 중 일부가 됩니다.

S와 P를 k라는 인덱스와 P라는 boolean 배열을 이용해서 나타내는 것입니다.

(맨 처음 초기 호출은 powerSet(null, S)로 S의 멱집합을 구하기 위한 호출입니다.)

 

 

 

 

 

< 함께 보면 좋은 자료 >

Java 재귀 함수(Recursion) 개념과 재귀 함수를 사용하는 이유

 

< 참고 자료 >

[ 개념 ] 09. 멱집합( Recursion )과 조합

 

# Java - 멱집합