[기초 수학] 조합

|  조합 (Combination)

✏️ 개념 정리

(1) 조합 : 서로 다른 N개의 수에서 R개를 뽑아 나열하는 경우의 수

- 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 X)

- nCr = n! / (n-r)!r! = nPr / r!  (단, 0 < r <= n)

 

(2) 중복 조합 : 순서 X, 중복 O

- nHr = n+r-1Cr

 

💻 구현하기

[ 조합 구현 _ 재귀 :  교환 없이 방문배열을 통해 출력하기 ]

✅  조합 : 서로다른 n개의 수에서 r개를 중복없이 순서를 고려하지 않고 나열하는 것

 

✅  구현 방법

 

[입력]

서로 다른 n개의 수를 담은 배열(int[] arr)과, 깊이 인덱스(depth), 배열의 길이(n), 선택하려는 갯수(r=2),

방문위치를 알려줄 배열(int[] visited)을 인자로 받는다.

*알고리즘이 시작되면, 선택 가능 갯수(r)는 처음입력받은 수(r=2)이다.

*깊이는 선택하려는 숫자의 인덱스를 의미한다.

*조합 알고리즘에서는 순서를 고려하지 않기 때문에, r을 기준으로 depth를 조정한다.

 

[처리]

선택 가능 갯수(r)를 기준으로, depth를 하나씩 방문하며 r == 0 일때에 출력한다.

 

※ 그림으로 본 조합 알고리즘 모습

✅  구현 하기

void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        if (depth == n) {
            return;
        }

        visited[depth] = true;
        combination(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        combination(arr, visited, depth + 1, n, r);
}