순열과 조합

유형	중복	순서	예시	공식
조합	❌	❌	A B, A C, B C	nCr
순열	❌	✅	A B, B A	nPr
중복 조합	✅	❌	A A, A B, B B	(n + r - 1)Cr
중복 순열	✅	✅	A A, A B, B A, B B	n^r

public class Permutation {
    private static int N,M;
    private static int[] sequence;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        
        sequence = new int[M]; // Array to store the current sequence
        visited = new boolean[N + 1]; // Boolean array to track visited numbers
        
        dfs(0); // Start generating permutations from depth 0
        System.out.println(sb.toString());
    }
    
    private static void dfs(int depth) {
        if (depth == M) {
            for(int num : sequence) {
                sb.append(num).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        for (int i = 1; i<=N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                sequence[depth] = i;
                dfs(depth+1);
                visited[i] = false;
            }
        
    }
}

O 초코 O 바닐라 O 딸기 O

칸막이 위치 설정

구분	순서 고려	중복 허용	대표 예시
순열	O	X	달리기 경주에서 순위 매기기
조합	X	X	대표 뽑기
중복순열	O	O	비밀번호 만들기
중복조합	X	O	과일 가게에서 과일 담기

1. 순열 (Permutation)

• 정의 : 서로 다른 n개에서 중복 없이 r개를 뽑아 순서대로 나열하는 경우의 수

• visited 배열을 사용해 한 번 사용한 원소는 다시 사용 X

1 // arr: {1, 2, 3}, r: 2  =>  [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]
    2 void permutation(int[] arr, int[] result, boolean[] visited, int index, int r) {
    3     if (index == r) {
    4         System.out.println(Arrays.toString(result));
    5         return;
    6     }
    7     for (int i = 0; i < arr.length; i++) {
    8         if (!visited[i]) {
    9             visited[i] = true;
   10             result[index] = arr[i];
   11             permutation(arr, result, visited, index + 1, r);
   12             visited[i] = false; // 백트래킹
   13         }
   14     }
   15 }

1. 중복순열 (Permutation with Repetition)

• 정의: 서로 다른 n개에서 중복을 허용하여 r개를 뽑아 순서대로 나열하는 경우의 수.

• 키워드: 순서 O, 중복 O

• 핵심 로직: 아무런 제약 없이 매번 모든 원소를 탐색합니다.

    1 // arr: {1, 2, 3}, r: 2  =>  [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]
    2 void permutationWithRepetition(int[] arr, int[] result, int index, int r) {
    3     if (index == r) {
    4         System.out.println(Arrays.toString(result));
    5         return;
    6     }
    7     for (int i = 0; i < arr.length; i++) {
    8         result[index] = arr[i];
    9         permutationWithRepetition(arr, result, index + 1, r);
   10     }
   11 }

1. 조합 (Combination)

• 정의: 서로 다른 n개에서 중복 없이 r개를 순서에 상관없이 뽑는 경우의 수.

• 키워드: 순서 X, 중복 X

• 핵심 로직: start 인덱스를 사용하여 현재 위치보다 이전의 원소들은 다시 보지 않도록 합니다.

    1 // arr: {1, 2, 3, 4}, r: 2  =>  [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]
    2 void combination(int[] arr, int[] result, int index, int start, int r) {
    3     if (index == r) {
    4         System.out.println(Arrays.toString(result));
    5         return;
    6     }
    7     for (int i = start; i < arr.length; i++) {
    8         result[index] = arr[i];
    9         combination(arr, result, index + 1, i + 1, r);
   10     }
   11 }

1. 중복조합

• 정의: 서로 다른 n개에서 중복을 허용하여 r개를 순서에 상관없이 뽑는 경우의 수.

• 키워드: 순서 X, 중복 O

• 핵심 로직: start 인덱스를 사용하되, 다음 재귀 호출 시 i + 1이 아닌 i를 넘겨주어 자기 자신을 다시 뽑을 수 있게 합니다.

    1 // arr: {1, 2, 3, 4}, r: 2  =>  [1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [3, 3], [3, 4], [4, 4]
    2 void combinationWithRepetition(int[] arr, int[] result, int index, int start, int r) {
    3     if (index == r) {
    4         System.out.println(Arrays.toString(result));
    5         return;
    6     }
    7     for (int i = start; i < arr.length; i++) {
    8         result[index] = arr[i];
    9         combinationWithRepetition(arr, result, index + 1, i, r);
   10     }
   11 }