[알고리즘] 순열, 조합, 부분 집합

순열, 조합, 부분 집합에 대해 공부 후 정리하였습니다.

1. 순열 (Permutation)

• 설명: 서로 다른 n개 중에서 r개를 순서 있게 뽑는 경우
• 시간 복잡도: O(n!)

public class Permutation {
    static int n = 3;
    static int r = 3;
    static int[] arr = {1, 2, 3};
    static boolean[] visited = new boolean[n];
    static int[] output = new int[r];

    public static void main(String[] args) {
        perm(0);
    }

    // 순열 생성 함수
    static void perm(int depth) {
        if (depth == r) {
            print(output);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                output[depth] = arr[i];
                perm(depth + 1);
                visited[i] = false;
            }
        }
    }

    static void print(int[] out) {
        for (int i : out) System.out.print(i + " ");
        System.out.println();
    }
}

2. 중복 순열 (Permutation with Repetition)

• 설명: 서로 다른 n개 중에서 중복을 허용하여 r개를 순서 있게 뽑는 경우
• 시간 복잡도: O(n^r)

public class RepeatedPermutation {
    static int n = 3;
    static int r = 2;
    static int[] arr = {1, 2, 3};
    static int[] output = new int[r];

    public static void main(String[] args) {
        permRep(0);
    }

    // 중복 순열 생성 함수
    static void permRep(int depth) {
        if (depth == r) {
            print(output);
            return;
        }

        for (int i = 0; i < n; i++) {
            output[depth] = arr[i];
            permRep(depth + 1);
        }
    }

    static void print(int[] out) {
        for (int i : out) System.out.print(i + " ");
        System.out.println();
    }
}

3. 조합 (Combination)

• 설명: 서로 다른 n개 중에서 r개를 순서 없이 뽑는 경우
• 시간 복잡도: O(nCr)

public class Combination {
    static int n = 4;
    static int r = 2;
    static int[] arr = {1, 2, 3, 4};
    static int[] output = new int[r];

    public static void main(String[] args) {
        comb(0, 0);
    }

    // 조합 생성 함수
    static void comb(int depth, int start) {
        if (depth == r) {
            print(output);
            return;
        }

        for (int i = start; i < n; i++) {
            output[depth] = arr[i];
            comb(depth + 1, i + 1);
        }
    }

    static void print(int[] out) {
        for (int i : out) System.out.print(i + " ");
        System.out.println();
    }
}

4. 중복 조합 (Combination with Repetition)

• 설명: 서로 다른 n개 중에서 중복을 허용하여 r개를 뽑는 경우
• 시간 복잡도: O(nHr) = O((n+r-1)Cr)

public class RepeatedCombination {
    static int n = 3;
    static int r = 2;
    static int[] arr = {1, 2, 3};
    static int[] output = new int[r];

    public static void main(String[] args) {
        combRep(0, 0);
    }

    // 중복 조합 생성 함수
    static void combRep(int depth, int start) {
        if (depth == r) {
            print(output);
            return;
        }

        for (int i = start; i < n; i++) {
            output[depth] = arr[i];
            combRep(depth + 1, i); // i부터 시작 (중복 허용)
        }
    }

    static void print(int[] out) {
        for (int i : out) System.out.print(i + " ");
        System.out.println();
    }
}

5. 부분 집합 (Subset)

• 설명: n개의 원소로 만들 수 있는 모든 부분 집합을 구함
• 총 경우의 수: 2ⁿ
• 시간 복잡도: O(2^n)

public class Subset {
    static int n = 3;
    static int[] arr = {1, 2, 3};
    static boolean[] selected = new boolean[n];

    public static void main(String[] args) {
        subset(0);
    }

    // 부분 집합 생성 함수
    static void subset(int depth) {
        if (depth == n) {
            printSubset();
            return;
        }

        // 현재 원소 포함
        selected[depth] = true;
        subset(depth + 1);

        // 현재 원소 미포함
        selected[depth] = false;
        subset(depth + 1);
    }

    static void printSubset() {
        System.out.print("{ ");
        for (int i = 0; i < n; i++) {
            if (selected[i]) System.out.print(arr[i] + " ");
        }
        System.out.println("}");
    }
}