Java 멱집합 구하기 (PowerSet)

멱집합 구하기

Stack과 Recursive를 이용하여, 멱집합 (Power Set) 을 구한다.

 

{1, 2, 3} 집합의 부분 집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이다. (공집합 포함)

Java 코드

재귀함수 search()

search() 메소드를 생성한다.

private static void search(Stack<Integer> stack, int k) {
    if(k >= n + 1) {
        System.out.println(stack.toString()); // 부분 집합을 출력한다.
    } else {
        // k를 부분집합에 포함한다.
        stack.add(k);
        search(stack, k + 1);

        // k를 부분집합에 포함하지 않는다.
        stack.pop();
        search(stack, k + 1);
    }
}

• 재귀를 돌리는데, k를 포함하는 경우와 포함하지 않는 경우, 2가지로 나눠서 수행한다.
• k 가 주어진 n + 1 보다 커지는 경우 재귀를 멈춘다.
• 그리고, stack에 들어있는 값들을 출력한다.

전체 코드

import java.util.Stack;

public class PowerSet {
    private static int n = 5;

    public static void main(String[] args) {
        final Stack<Integer> stack = new Stack<>();
        search(stack, 1);
    }

    private static void search(Stack<Integer> stack, int k) {
        if(k >= n + 1) {
            System.out.println(stack.toString()); // 부분 집합을 출력한다.
        } else {
            // 1. k를 부분집합에 포함한다.
            stack.add(k);
            search(stack, k + 1);

            // 2. k를 부분집합에 포함하지 않는다.
            stack.pop();
            search(stack, k + 1);
        }
    }
}

 

응용

주어진 문자들의 멱집합 구하기

package recursive;

import java.util.Stack;

public class PowerSet {
    private static final char[] characters = {'A', 'B', 'C', 'D', 'E'};

    public static void main(String[] args) {
        final Stack<Character> stack = new Stack<>();
        search(stack, 0);
    }

    private static void search(Stack<Character> stack, int k) {
        if(k >= characters.length) {
            System.out.println(stack.toString());
        } else {
            stack.push(characters[k]);
            search(stack, k+1);

            stack.pop();
            search(stack, k+1);
        }
    }
}