PowerSet(부분집합)

PowerSet (부분집합)

부분집합을 구하는 3가지 방법

1. 조합을 이용한 방법

n개중 r개를 선택하는 조합알고리즘을 이용하여

for문으로 r을 0부터 n까지 선택한 결과.

2. 재귀함수를 이용하는 방법

1. 현재 인덱스를 포함하는 경우
2. 현재 인덱스를 포함하지 않는 경우

위 2가지 경우를 재귀호출하여 인덱스가 모든 배열을 순회했을때 결과.

3. 비트연산을 이용하는 방법

집합의 개수가 4개라면 0000~1111을 순회하며 해당 비트가 1인지를 확인하는 방법

code

public class Main {
    static boolean[] visit;

    public static void main(String[] args) {
        int N = 4;
        visit = new boolean[N];

        for (int i = 0; i <= N; i++) {
            combination(N, i, 0, 0); //N개중 i개를 뽑은 모든경우
        }
        System.out.println("----------------------");

        powerSet(visit.length, 0);
        System.out.println("----------------------");

        bit(N);

    }
    //조합
    private static void combination(int n, int r, int depth, int start) {
        if (depth == r) {
            // print
            for (int i = 0; i < visit.length; i++) {
                if (visit[i])
                    System.out.print(i + " ");
            }
            System.out.println();
            return;
        }
        for (int i = start; i < n; i++) {
            if (visit[i] == false) {
                visit[i] = true;
                combination(n, r, depth + 1, i);
                visit[i] = false;
            }
        }
    }

    // 재귀호출을 이용한 방법
    static void powerSet(int n, int idx) {
        if (idx == n) {
            // print
            for (int i = 0; i < visit.length; i++) {
                if (visit[i])
                    System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        // 현재 인덱스를 포함하는 경우
        visit[idx] = true;
        powerSet(n, idx + 1);

        // 현재 인덱스를 포함하지 않는 경우
        visit[idx] = false;
        powerSet(n, idx + 1);
    }

    // Bit연산을 이용하는 방법
    static void bit(int n) {
        for (int i = 0; i < 1 << n; i++) {// n이 4일때, 0000~1111
            for (int j = 0; j < n; j++) { // 0001, 0010, 0100, 1000
                // 각 자리 논리합(AND)의 결과가 0이 아닐경우
                // (해당bit를 포함함을 의미)
                if ((i & 1 << j) != 0)
                    System.out.print(j + " ");
            }
            System.out.println();
        }
    }

}