알고리즘 - 순열(Permutation)과 조합(Combination)

순열

• 서로 다른 n개에서 r개를 뽑아서 정렬하는 경우의 수
• DFS 이용
• 시간 복잡도: O(P(n, r)) = O(n! / (n-r)!)

순열 예제: 5P3

public class Permutation {
    public static void main(String[] args) {
        int n = 5;
        int[] arr = {1, 2, 3, 4, 5};
        int[] output = new int[3]; // 결과를 저장할 배열
        boolean[] visited = new boolean[n]; // 방문 여부를 체크할 배열

        // 순열 함수 호출
        permutation(arr, output, visited, 0, n, 3);
    }

    // 순열 생성 함수
    static void permutation(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
        // 깊이가 r에 도달하면 출력
        if (depth == r) {
            print(output, r);
            return;
        }

        // 각 요소에 대해 방문 여부를 확인하고 순열 생성
        for (int i = 0; i < n; i++) {
            if (!visited[i]) { // 현재 요소가 방문되지 않았을 때
                visited[i] = true; // 방문 표시
                output[depth] = arr[i]; // 현재 깊이에 해당 요소 저장
                permutation(arr, output, visited, depth + 1, n, r); // 다음 깊이로 재귀 호출
                visited[i] = false; // 방문 표시 해제
            }
        }
    }

    // 배열 출력 함수
    static void print(int[] arr, int r) {
        for (int i = 0; i < r; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

조합

• n개의 숫자 중에서 r개의 수를 순서 없이 뽑는 경우의 수
• 백트랙킹 이용
• 시간 복잡도: O(C(n, r)) = O(n! / (r! * (n-r)!))

조합 예제: 5C3

public class Combination {
    public static void main(String[] args) {
        int n = 5;
        int[] arr = {1, 2, 3, 4, 5};
        boolean[] visited = new boolean[n]; // 방문 여부를 체크할 배열

        // n개의 숫자 중에서 3개의 수를 뽑는 조합 생성
        combination(arr, visited, 0, n, 3);
    }

    // 조합 생성 함수
    static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
        // 선택한 요소가 r개가 되면 출력
        if (r == 0) {
            print(arr, visited, n);
            return;
        }

        // 백트래킹을 사용하여 조합 생성
        for (int i = start; i < n; i++) {
            visited[i] = true; // 방문 표시
            combination(arr, visited, i + 1, n, r - 1); // 다음 요소를 선택하여 재귀 호출
            visited[i] = false; // 방문 표시 해제
        }
    }

    // 조합 출력 함수
    static void print(int[] arr, boolean[] visited, int n) {
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }
}

---

ref.
https://bcp0109.tistory.com/14
https://jforj.tistory.com/38