멱집합 (powerset)

uglyduck.dev·2020년 9월 26일

algorithm

알고리즘 🧮

목록 보기

8/16

문제

임의의 집합 data의 모든 부분집합을 출력하라.
data = {a , b, c, d}
2^4 = 16개

힌트

1 STEP

{a,b,c,d,e,f}의 모든 부분집합을 나열하려면
- a를 제외한 {b,c,d,e,f}의 모든 부분집합들을 나열하고
- {b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다.

2 STEP

{b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면
- {c,d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고
- {c,d,e,f}의 모든 부분집합에 {a,b}를 추가한 집합들을 나열한다.

3 STEP

{c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면
- {d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고
- {d,e,f}의 모든 부분집합에{a,c}를 추가한 집합들을 나열한다.

Pseudo code

powerSet(S) // Mission: S의 멱집합을 출력하라

if S is an empty set // Base case
    print nothing;
else
    let t be ther first element of S;
    find all subsets of S-{t} by calling powerSet(S-{t});
    print the subset;
    print the subsets with adding t;

이렇게 하려면 powerSet 함수는 여러 개의 집합들을 return해야 한다. 어떻게?

powerSet(P, S)// Mission: S의 멱집합을 구한 후 각각에 집합 P를 합집합하여 출력하라

if S is an empty set
    print P;
else
    let t be ther first element of S;
    powerSet(P, S-{t}); // t 포함 X
    powerSet(PU{t}, S-{t}); // t 포함**

recursion 함수가 두 개의 집합을 매개변수로 받도록 설계해야 한다는 의미이다. 두 번째 집합의 모든 부분집합들에 첫번째 집합을 합집합하여 출력한다.

두 집합의 표현

Mission: S의 멱집합을 구한 후 각각에 집합 P를 합집합하여 출력하라

두 집합의 표현

집합 S는 data[K], ... , data[n-1]이고, 집합 P는 include[i]=true, i=0, .. , k-1, 인 원소들이다.

Powerset

Mission: data[k], ... ,data[n-1]의 멱집합을 구한 후 각각에 inlcude[i]=true, i=0, .. ,k-1, 인 원소를 추가하여 출력하라.

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) {
        for (int i = 0; i < n; i++)
            if (include[i]) System.out.print(data[i] + " ");
        System.out.printaln();
        return;
}
include[k] = false; 
powerSet(k+1);
include[k] = true; 
powerSet(k+1);
}