Recursion 응용(4)

멱집합 (powerset)

의미

- 어떤 집합의 모든 부분집합들의 집합이다.

- data = {a, b, c, d}의 모든 부분집합을 출력한다면(멱집합)

∅, a, b, c, d, ab, ac, ad, bc, bd, cd, abc, abd, acd, bcd, abcd가 있다.

이는 $2^4$개로서 총 16개라 할 수 있다.

멱집합을 구하는 방법

- {a, b, c, d, e, f}의 모든 부분집합을 나열하고자 한다.

1) a를 제외한 {b, c, d, e, f}의 모든 부분집합들을 나열한다.

2) {b, c, d, e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다.

-이는 곧 a를 포함하지 않은 부분집합의 수인 $2^5$와 포함한 부분집합의 수인 $2^5$가 합해져 총 $2^6$개가 된다.  

- {b, c, d ,e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다 할 때

1) {c, d, e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다.

2) {c, d, e, f}의 모든 부분집합에 {a, b}를 추가한 집합들을 나열한다.

- 이 방법을 recursive하게 계속 반복하게 된다면 결국 원하는 결과를 얻을 수 있게 된다.

슈도 코드

powerSet (S)

if S is an empty set //S가 공집합이라면

print nothing;

else

let t be the first element of S; //집합에서의 한 원소 t를 고른다.

find all subsets of S - {t} by calling powerSet(S - {t}); //t를 제외한 모든 부분집합을 구한다.

print the subsets;

print the subsets with adding t;

-> 이 슈도 코드에서의 powerSet함수는 여러 개의  집합들을 반환해야 한다.

-개선

powerSet (P, S) //초기값은 powerSet (∅, data);로 주어 시작하면 된다.

if S is an empty set

print P;

else

let t be the first element of S;

powerSet (P, S - {t}); //t를 포함하지 않은 집합

powerSet (P ∪ {t}, S - {t}); //t를 포함한 집합

-> 이 슈도코드에서는 순환함수가 두 개의 집합을 별도의 매개변수로 받도록 설계하였다.

-> 두 번째 집합의 모든 부분집합에 첫 번째 집합을 합집합한 후 출력을 한다.

- 위 슈도코드에 따라 {b, c, d, e, f}의 모든 부분집합에 {a}를 추가한다 하였을 때

{c, d, e, f}가 S로 k번째부터 마지막 원소까지 연속된 원소들이다.

{a, b}를 추가한 집합들이나 {a}를 추가한 집합들이 P라 할수 있으며 처음부터 k - 1번째 원소들 중 일부이다.

- 집합 S는 k번째 인덱스 이후 마지막 인덱스인 n - 1번째 인덱스까지의 집합이다.

- P는 k번째 인덱스 앞의 원소들 중 일부인데 이를 표시하기 위해서는 include함수를 통해 true / false로 구분한다. 또한 include함수에서의 true반환 인덱스들의 집합이다.

구현

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) { //k또한 트리상에서 현재 위치를 표시한다.

if (k == n) { //만일 위치가 리프 노드라면

for (int i = 0; i < n; i++)

if (include[i])

System.out.println(data[i] + " ");

System.out.println();

return;

}

include[k] = false;

powerSet (k + 1); //왼쪽으로 먼저 내려간다.

include[k] = true;

powerSet (k + 1); //오른쪽으로 내려간다.

}

-> 이 프로그램을 실행할 때는 초기값을 powerSet(0)으로 실행하여 P를 공집합으로, S를 전체집합으로 설정한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class PowerSetProblem {
    static char data[]; //멱집합을 구하고자 하는 배열
    static int n; //데이터배열의 총 길이를 나타내는 변수
    static boolean[] includes; //P의 원소를 가리켜주는 배열
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        bw.write("멱집합을 구하고자 하는 문자들을 입력해주세요(띄어쓰기 없이) : ");
        bw.flush();
        
        String input = br.readLine();
        data = input.toCharArray();
        n = data.length;
        includes = new boolean[n];
        
        powerSet(0);
        bw.close();
    }
    
    
    static void powerSet (int k) throws Exception {
        if (k == n) {
            for (int i = 0; i < n; i++)
                if (includes[i])
                    bw.write(String.valueOf(data[i]) + " ");
            bw.write("\n");
            bw.flush();
            return;
        }
        
        includes[k] = false;
        powerSet(k + 1);
        includes[k] = true;
        powerSet(k + 1);
    }
}