[알고리즘] | 조합(Combination)

조합이란?

서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합(combination)이라고 하고 nCr이라고 표현한다.

조합의 수식

• nCr = n!/(n-r)! * r!, (n >=r)
• nCr = n-1Cr-1 + n-1Cr (재귀적 표현)
• nC0 = 1

조합을 생성하는 방법

1. 재귀호출을 사용하여 조합생성
2. NextPermutation을 사용하여 조합생성.

NextPermutation을 사용하여 조합생성

1. 원소크기와 같은 int 배열(select)을 생성하여 뽑을 r개의 크기만큼 뒤에서 0이아닌 값(예를 들어 1)으로 초기화한다.
2. nextPermutation 알고리즘을 사용한다.
3. nextPermutation 알고리즘을 수행할때마다 조합이 만들어진다. (nextPermutation 과정 수행시마다 0이 아닌 값의 위치가 변경된다.)
4. select 배열에서 0이 아닌 값을 갖고 있는 위치에 해당하는 원소가 조합에 선택된 원소이다.

조합의 시간복잡도

1. 재귀를 사용하여 구현한 조합의 시간복잡도: O(2ⁿ)
2. NextPermutation을 사용하여 구현한 조합의 시간복잡도: O(n)

조합과 수열의 차이

순열과 조합의 차이는 순서에 있다.

순열은 n개에서 순서를 가지고 r개를 뽑아 한줄로 나열한다. 따라서 순서가 바뀐다면 원소들이 같아도 다른 순열이다.
반면, 조합은 n개에서 r개를 뽑을뿐 순서를 가지고 나열하지 않는다. 즉, 순서가 바뀌어도 원소들이 같다면 같은 조합이다.

즉, 순열은 순서가 있는 조합이라고 볼 수 있다.

예제코드

[재귀를 사용하여 조합생성]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class CombinationTest {

    public static void main(String[] args) throws IOException {
        final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        final int numberCount = Integer.parseInt(bufferedReader.readLine());
        final int combinationCount = Integer.parseInt(bufferedReader.readLine());

        final int[] input = new int[numberCount];
        final int[] combination = new int[combinationCount];

        final StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for (int i = 0; i < numberCount; i++) {
            input[i] = Integer.parseInt(stringTokenizer.nextToken());
        }


        combination(input, combination, 0, 0);
    }

    private static void combination(final int[] input, final int[] combination, final int count, final int start) {
        if (count == combination.length) {
            System.out.println(Arrays.toString(combination));
            return;
        }

        for (int i = start; i < input.length; i++) {
            combination[count] = input[i];
            combination(input, combination, count + 1, i + 1);
        }

    }

}

[NextPermuatation을 사용하여 조합생성]

public class CombinationTest_NextPer {

    public static void main(String[] args) throws IOException {
        final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        final int numberCount = Integer.parseInt(bufferedReader.readLine());
        final int combinationCount = Integer.parseInt(bufferedReader.readLine());

        final int[] input = new int[numberCount];
        final int[] select = new int[combinationCount];

        final StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for (int i = 0; i < numberCount; i++) {
            input[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        int count = 0;
        while (++count <= combinationCount) {
            select[combinationCount - count] = 1;
        }

        do {
            for (int i = 0; i < select.length; i++) {
                if (select[i] == 1) {
                    System.out.print(input[i] + " ");
                }
            }
            System.out.println();
        } while (nextPermutation(input));

    }

    private static boolean nextPermutation(final int[] input) {
        int i = input.length - 1;

        while (i > 0 && input[i - 1] >= input[i]) {
            i--;
        }

        if (i == 0) {
            return false;
        }

        int j = input.length - 1;

        while (input[i - 1] >= input[j]) {
            j--;
        }

        swap(input, i - 1, j);

        int k = input.length - 1;
        while (i < k) {
            swap(input, i++, k--);
        }

        return true;
    }

    private static void swap(final int[] input, final int i, final int j) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }

}