조합(combination)

conbrio·2022년 3월 5일

조합

조합의 정의

조합론에서 조합(組合, 문화어: 무이, 영어: combination)은 서로 다른 $n$ 개의 원소를 가지는 어떤 집합 (사실, 집합은 서로 다른 원소의 모임으로 정의된다.)에서 순서에 상관없이 $r$ 개의 원소를 선택하는 것이며, (즉, 선택의 순서와 상관없이 같은 원소들이 선택되었다면 같은 조합이며 다른 원소들이 선택되었다면 다른 조합이다.) 이는 $n$ 개의 원소로 이루어진 집합에서 $r$ 개의 원소로 이루어진 부분집합을 만드는 것 혹은 찾는 것과 같다. 가능한 조합의 수는 이항계수와 같다.

출처 : 위키백과 - 조합

조합이란 위 설명과 같이 서로 다른 n개 원소를 가지는 어떤 집합에서 r개의 원소를 선택하는 것입니다. 이때 중복은 허용하지 않으며, 순서는 고려하지 않습니다.

이 때, 조합의 수는 $_nC_r$ 로 표현되며, 이는 $\frac{n!}{k!\cdot(n-k)!}$ 과 같습니다.

즉, {1, 2, 3}의 집합에서 2개의 원소를 선택하는 조합은

{1, 2}
{2, 3}
{1, 3}

의 3개이며, 이는 $_3C_2=\frac{3!}{2!\cdot1!}=3$ 으로 위 식으로 계산이 가능합니다.

구현

구현은 재귀함수를 이용하여 이루어집니다.

각 반복마다 하나씩 원소를 순회하며, 해당 원소를 선택할지, 선택하지 않을지를 결정합니다.
매 선택마다 함수의 parameter를 증가시켜 모든 선택이 끝났는지, 혹은 $r$ 개의 원소를 선택하지 못하고 순회를 마쳤는지를 판단하고, 선택이 끝났다면 선택된 원소들만을 출력합니다.

재귀가 끝나는 기저사례(base case) : $r$ 개의 원소를 선택 완료. 혹은 모든 원소 순회 완료

재귀 사례(recursive case) : 원소를 선택 혹은 선택하지 않고 다음 원소를 순회

아래 combination1메서드와 combination2메서드는 비슷하지만 약간 다른 방식으로 구현한 조합 알고리즘 입니다.

combination1은 해당 원소를 선택하는 경우에만 재귀 호출, 선택하지 않는 경우에는 for문의 다음 반복으로 넘어가게 한 것이고,
combination2는 해당 원소를 선택하는 경우와 선택하지 않는 경우 모두 재귀 호출하도록

했다는 점에서 차이가 있습니다.

import java.util.Arrays;

public class CombinationTest {
    public static void main(String[] args) {
        int[] input = {1, 2, 3, 4};
        int target = 2;
        System.out.println("조합1");
        combination1(input, new int[target], target, 0, 0);
        System.out.println("\n조합2");
        combination2(input, new int[target], target, 0, 0);
    }

    public static void combination1(int[] input, int[] output, int r, int selected, int start) {
        if (selected == r) {
            // r개 선택이 끝난 경우 출력
            System.out.println(Arrays.toString(output));
            return;
        }

        for (int i = start; i < input.length; i++) {
            // 현재 원소를 선택하고 재귀 호출
            // 선택이 되었으므로 재귀 호출 시 start 는 i + 1, r 은 r - 1
            output[selected] = input[i];
            combination1(input, output, r, selected + 1, i + 1);

            // 현재 원소를 선택하지 않은 상태로 다음 원소로 넘어감
        }
    }

    public static void combination2(int[] input, int[] output, int r, int selected, int count) {
        if (selected == r) {
            // r개 선택이 끝난 경우 출력
            System.out.println(Arrays.toString(output));
            return;
        }
        if (count == input.length) {
            // r개 선택이 되지 않은 상태로 모든 원소의 순회가 끝난 경우 종료
            return;
        }

        // 현재 원소를 선택
        output[selected] = input[count];
        combination2(input, output, r, selected + 1, count + 1);

        // 현재 원소를 선택하지 않음
        combination2(input, output, r, selected, count + 1);
    }
}

combination1과 combination2 메서드는 for문을 사용 여부에서 차이가 있지만 본질적으로는 같습니다.
input 배열의 원소들을 순회하며 output 배열에 선택한 원소들의 값을 넣고, selected 변수가 r과 같아지면 output 배열을 출력하도록 했습니다.
위 코드는 아래와 같이 출력됩니다.

조합1
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

조합2
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

combination2 메서드는 부분집합 - 멱집합과 거의 비슷하니 함께 참고합시다.

연습문제

백준 - N과 M (1)

중복조합

중복조합의 정의

중복조합(重複組合, combination with repetition)은 서로 다른 $n$ 개의 원소에서 중복을 허락하여 $k$ 개를 뽑는 경우이다.

출처 : 위키백과 - 조합

쉽게 말해서 위에서 설명한 기존의 조합에서 중복을 허용한 것으로 볼 수 있습니다.

구현

아래 코드는 위 combination1 메서드에서 start + 1을 start로 바꾸어 다음 재귀시에도 현재 선택한 원소를 다시 선택할 수 있게 해준 것입니다.

import java.util.Arrays;

public class CombinationTest {
    public static void main(String[] args) {
        int[] input = {1, 2, 3, 4};
        int target = 2;
        System.out.println("중복조합");
        reCombination(input, new int[target], target, 0, 0);
    }

    public static void reCombination(int[] input, int[] output, int r, int selected, int start) {
        if (selected == r) {
            // r개 선택이 끝난 경우 출력
            System.out.println(Arrays.toString(output));
            return;
        }

        for (int i = start; i < input.length; i++) {
            // 현재 원소를 선택하고 재귀 호출
            // 선택이 되었으므로 재귀 호출 시 start 는 i + 1, r 은 r - 1
            output[selected] = input[i];
            reCombination(input, output, r, selected + 1, i);

            // 현재 원소를 선택하지 않은 상태로 다음 원소로 넘어감
        }
    }
}