[Java] 완전탐색: 순열, 조합, 부분집합

1. 순열

public class Permutation {
    static char[] arr;
    static int R;   // 만들 순열의 길이
    static int[] selected;  // 고른 값들의 인덱스를 저장하는 배열 (길이: R)

    /**
     * 중복 허용하는 경우
     */
    static void perm1(int r) {	// r: 현재까지 고른 개수
        if (r == R) {
            for (int i = 0; i < R; i++) System.out.print(arr[selected[i]]);
            System.out.println();
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            selected[r] = i;
            perm1(r + 1);
        }
    }

    /**
     * 중복 허용하지 않는 경우
     */
    static boolean[] isSelected;    // 현재 탐색할 인덱스가 지금 만들고 있는 순열에 포함되어있는지 구분
    static void perm2(int r) {
        if (r == R) {
            for (int i = 0; i < R; i++) System.out.print(arr[selected[i]]);
            System.out.println();
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (isSelected[i]) continue;
            isSelected[i] = true;
            selected[r] = i;
            perm2(r + 1);
            isSelected[i] = false;
        }
    }

    public static void main(String[] args) {
        arr = new char[] {'A', 'B', 'C', 'D'};
        R = 2;	// 2개 고르는 순열의 경우
        selected = new int[R];
        isSelected = new boolean[arr.length];

        perm1(0);
        // AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD
        perm2(0);
        // AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC
    	}
    }

 

2. 조합

public class Combination {
    static int R;
    static char[] arr;
    static char[] selected;
    static boolean[] visited;

    static void combination(int r, int start) {
        if (r == R) {
            for (char c : selected) System.out.print(c);
            System.out.println();
            return;
        }

        for (int i = start; i < arr.length; i++) {
            if (visited[i]) continue;
            selected[r] = arr[i];
            visited[i] = true;
            combination(r + 1, i + 1);
            visited[i] = false;
        }
    }

    public static void main(String[] args) {
        R = 2;  // 2개를 뽑는 조합
        arr = new char[] {'A', 'B', 'C', 'D'};
        selected = new char[R];
        visited = new boolean[arr.length];

        combination(0, 0);
    }
}

 

3. 부분집합

public class Subset {
    static char[] arr;
    static int N;
    static boolean[] included;

    static void subset(int n) {
        // 종료 조건: 전체 개수에 도달
        if (n == N) {
            for (int i = 0; i < N; i++) {
                if (included[i]) System.out.print(arr[i]);
            }
            System.out.println();
            return;
        }

        included[n] = true;
        subset(n + 1);

        included[n] = false;
        subset(n + 1);

    }

    public static void main(String[] args) {
        arr = new char[] {'A', 'B', 'C', 'D'};
        N = arr.length;
        included = new boolean[N];

        subset(0);
    }
}