[조합]01. 조합의 구현

조합의 정의

조합은 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 말한다. 앞서 살펴본 순열과의 차이점은 순서를 고려하지 않는다는 점이다.

수학적 증명을 통한 조합 구하기

순열이 nPr = n개에서 r개를 선택한 후 순서대로 나열하는 것인데 여기서 n개에서 r개를 선택하는 것이 순열이고 이 r개를 다시 나열하는 것이 nPr이다. 따라서 nCr은 다음과 같이 구할 수 있다.

 

위 식을 처리하기 쉬운 재귀 방식으로 변경해보자.

위 식을 잘 살펴보면 nCr은 보다 낮은 단계인 n-1Cr-1과 n-1Cr의 합이다. 여기서 r이 선택할 요소의 개수이다. 즉 n개에서 r개를 뽑는 방법은 어떤 요소 하나를 고려했을 때 그 요소를 뽑았을 때의 조합과 그 요소를 뽑지 않았을 때의 조합의 합이된다.

조합의 과정

{'A', 'B', 'C'} 로 구성된 배열에서 2개의 원소를 선택하는 조합의 경우 즉 3C2를 살펴보자. 

과정에서는 3개의 변수가 등장하는데 n은 전체 개수인 3, r은 뽑아야 할 개수로 2, i는 검사하는 요소의 index로 0이다. 

다음 그림은 최초의 상태이다.

 

i가 0이므로 A가 선택되고 하나가 선택되었으므로 r즉 뽑아야할 개수는 1로 줄어든다. 

i가 증가해서 1인 상태로 다음 동작이 진행되고 B를 선택하면 r=0이 된다. 즉 뽑아야할 요소들을 다 뽑았으므로 출력하고 리턴하면 된다.

 

리턴되었으므로 기존 스택으로 돌아가서 i를 1증가해서 2로 만든 후 아직 r=1이므로 새로운 요소 C를 선택한다. 

 

다시 리턴되고 기존 스택에 가서 i를 1증가시켜 3을 만든 후 r=1이므로 새로운 요소를 선택하려 하지만 i==3인 요소는 없으므로 스택이 종료된다.

 

드디어 A가 선택되었을 때의 흐름이 끝났다. 이제 A가 선택되지 않았을 때의 흐름이 이뤄진게 된다.(처음에 이야기했듯이 조합은 고려하는 요소가 선택됐을 때의 조합과 그 요소를 선택하지 않았을 때의 조합의 합이다.)

최초의 스택으로 이동해서 i=1인 상태로 변경되므로 B가 선택되고 r=1이 된다.

다음 단계로 C가 선택되고 B, C가 출력되고 리턴된다.

 

상위 스택으로 이동 후 i가 3인 상태에서 다음을 찾지만 존재하지 않으므로 스택이 종료된다.

 

여기까지가 B 요소가 선택되었을 때의 동작이 종료된다. 다시 B가 선택되지 않았을 때의 동작이 시작될 차례이다.

 

C가 선택되고 r=1이 된다. 하지만 여기서 다음 요소를 찾아야 하는데 없으니까 종료된다.

 

여기까지가 C가 선택되었을 때의 동작이다. 다시 C가 선택되지 않았을 경우를 살펴 보면 더이상 선택지가 없으므로 바로 종료되고 비로서 모든 스택이 종료, 조합의 과정이 완료된다.

 

결과적으로 {'A', 'B', 'C'}로 이뤄진 배열에서 2개를 선택하는 방법은 AB, AC, BC 3가지가 출력되면 정상이다.

 

자바코드

위 과정을 자바 코드로 옮겨보자.

    /**
     * src 배열에서 r개의 요소를 선택하는 경우를 출력한다.
     * @param src   원본 배열
     * @param r     고를 원소의 개수
     * @param i     선택되는 요소의 index(초기는 0)
     * @param temp  선택된 요소들이 저장되는 배열
     */
    private static void makeCombination(char[] src, int r, int i, char[] temp) {
        if (r == 0) {
            System.out.println(Arrays.toString(temp));
            return;
        } else if (i == src.length) {
            return;
        } else {
            temp[src.length - 1 - r] = src[i];
            makeCombination(src, r - 1, i + 1, temp);   // 요소를 선택했을 때
            makeCombination(src, r, i + 1, temp);       // 요소를 선택하지 않았을 때
        }
    }