순열(Permutation)과 조합(Combination)

순열 

 

: 서로 다른 n개의 원소에서 r개를 중복없이 순서를 고려하여 선택하는 것  (단, 0 < r ≤ n)

 

[1, 2, 3] 배열에서 2개를 뽑을 때, [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] 가 만들어진다.

 

필요한 인자

 

int [] nums : n개의 숫자 배열 

int [] output : 결과물을 저장할 output 배열

boolean [] visited : 방문 확인을 위한 배열

int depth : 몇개의 숫자가 선택되었는지 깊이

 

코드 (java 재귀로 구현)

public static void permutation(int [] nums, int [] output, boolean [] visited, int depth) {
    // 깊이가 r개 일 경우 (r개의 수가 모두 선택된 경우)
    if (depth == output.length) {
        // 결과 출력
        for (int num : output) {
            System.out.print(num + " ");
        }
        System.out.println();
        return;
    }

    // 다른 순서일 경우
    for (int i = 0; i < nums.length; i++) {
        // 중복없이 숫자를 선택하기 위해 방문 확인
        if (!visited[i]) {
            // 해당 숫자 방문 처리
            visited[i] = true;
            output[depth] = nums[i];
            // 깊이 증가 후, 다시 호출
            permutation(nums, output, visited, depth + 1);
            // 방문 해제
            visited[i] = false;
        }
    }
}

 

호출 코드

int n = 3;
int r = 2;
int [] nums = {1,2,3};
        
// [1, 2, 3] 중에 서로 다른 2개(순서 고려 O)의 숫자를 뽑도록 구현
permutation(nums, new int[r], new boolean[n], 0);

---

조합

 

: 서로 다른 n개의 원소에서 r개를 중복없이 순서를 고려하지 않고 선택하는 것  (단, 0 < r ≤ n)

 

[1, 2, 3] 배열에서 2개를 뽑을 때, [1, 2] [1, 3] [2, 3] 가 만들어진다.

즉, 현재 숫자 다음에 뽑힐 숫자는 배열에서 현재 숫자의 인덱스보다 높은 인덱스에서만 선택한다.

(그래서 순열과 다르게 인자로 start를 필요로한다.)

 

필요한 인자

 

int [] nums : n개의 숫자 배열

int [] output : 결과물을 저장할 output 배열

boolean [] visited : 방문 확인을 위한 배열

int depth : 몇개의 숫자가 선택되었는지 깊이

int start : 확인된 숫자 인덱스

 

코드 (java 재귀로 구현)

public static void combination(int[] nums, int[] output, boolean[] visited, int depth, int start) {
    // 깊이가 r개 일 경우 (r개의 수가 모두 선택된 경우)
    if (depth == output.length) {
        // 결과 출력
        for (int num : output) {
            System.out.print(num + " ");
        }
        System.out.println();
        return;
    }

    // 해당 수 위부터 수 추가 가능 (순서 고려 안하므로)
    for (int i = start; i < nums.length; i++) {
        // 중복없이 숫자를 선택하기 위해 방문 확인
        if (!visited[i]) {
            // 해당 숫자 방문 처리
            visited[i] = true;
            output[depth] = nums[i];
            // 깊이 증가 후, 다시 호출
            combination(nums, output, visited, depth + 1, i + 1);
            // 방문 해제
            visited[i] = false;
        }
    }
}

 

호출 코드

int n = 3;
int r = 2;
int [] nums = {1,2,3};
        
// [1, 2, 3] 중에 서로 다른 2개(순서 고려 X)의 숫자를 뽑도록 구현
combination(nums, new int[r], new boolean[n], 0, 0);

---

추가 꿀 팁!

위에 코드들은 순열, 조합 다 중복을 고려하지 않는다. 

중복을 고려하고 싶으면 위에 코드에서 방문 확인(visited 배열 관련) 코드를 빼면 된다.