조합과 중복조합

저번 포스트에 이어 이번에는 조합과 중복조합에 대해 정리하고자 합니다.

 

조합

먼저 조합입니다. 조합은 "N개의 숫자 중에서 R개의 숫자를 순서 없이 뽑는 것"을 말합니다.

예를 들어 1, 2, 3 이라는 숫자가 있을 경우, 여기 2개의 숫자를 순서 없이 뽑으면

{1, 2}, {1, 3}, {2, 3} 을 얻을 수 있습니다. 

순열이었다면 {2, 1}, {3, 1}, {3, 2} 등을 얻을 수 있었지만, 

조합은 순열과 달리 순서 없이 뽑기 때문에 제외합니다.

 

그렇다면 이제 이를 구현해보기 위해 필요한 것들을 생각해보면,

조합을 구하고자 하는 데이터(숫자)와,

조합에 현재 숫자가 뽑혔는지를 알아야 합니다.

 

그리고 이를 구현하는 방법은 2가지가 있습니다.

백트래킹을 이용하거나, 재귀 호출을 이용할 수 있습니다.

 

백트래킹을 이용한 조합

기준이 되는 변수를 하나 사용합니다. (start)

이를 기준으로 작은 인덱스라면 뽑을 후보에서 제외하고, 큰 인덱스라면 뽑을 후보가 됩니다.

start는 0부터 시작하여, 우선 start 인덱스에 있는 숫자를 뽑습니다.

그리고 이 숫자를 이미 뽑혔음을 표시하고, 다시 함수를 호출합니다.

이때는 start 이후의 숫자들을 확인해야 하므로, + 1 증가시켜 다음 함수로 전달됩니다.

 

private static int[] array = {1,2,3,4};

public static void main(String[] args) {
    combination(new boolean[array.length], 0, 4, 3);
}

private static void combination(boolean[] visited, int start, int n, int r) {
    if (r == 0) {
    	// 방문한 숫자들만 출력
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
            	System.out.print(array[i] + " ");
            }
        }
        System.out.println();
        return;
    }
	
    for(int i = start; i < n; i++) {
    	// i는 방문했음을 표시
        visited[i] = true;
        // i 이후의 숫자들에 대해 탐색하기 위해 i + 1
        // 이미 한 개가 뽑혔으므로 r - 1
        combination(visited, i + 1, n, r - 1);
        // i를 뽑은 경우에 대한 조합이 만들어졌을 것이기에 i는 더 이상 뽑지 않으므로 이를 표시
        visited[i] = false;
    }
}

 

재귀호출을 이용한 조합

start처럼 기준이 되는 인덱스를 하나 사용합니다. (depth)

이 인덱스는 현재 인덱스를 나타냅니다.

현재 인덱스를 뽑을 거라면 true를 표시하고, 그렇지 않다면 false입니다.

각 경우에 대해 재귀 호출을 수행하고,

매 재귀 호출마다 R개가 채워졌는지 확인합니다.

 

private static int[] array = {1,2,3,4};

public static void main(String[] args) {
    combination(new boolean[array.length], 0, 4, 3);
}

private static void combination(boolean[] visited, int depth, int n, int r) {
	// r개를 완성했다면 출력
    if(r == 0) {
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
            	System.out.print(array[i] + " ");
            }
        }
        System.out.println();
        return;
    }
	
    // 현재 인덱스가 배열을 넘어서는 경우
    if (depth == n) {
        return;
    }

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

    visited[depth] = false;
    // 현재 인덱스는 뽑지 않을 것이므로 r은 그대로 전달
    combination(visited, depth + 1, n, r);
}

---

중복조합

중복조합은 중복순열에서도 그렇듯, 자기 자신을 포함할 수 있게 된 조합입니다.

따라서, 어떤 숫자가 뽑혔는지 확인할 필요가 없어졌습니다.

아래 구현은 재귀호출을 이용한 방식이고,

target 배열에 중복조합이 저장됩니다.

index는 target 배열에 접근하는 인덱스이고, depth는 array 배열에 접근하는 인덱스입니다.

 

ç

public static void main(String[] args) {
    combination(new int[3], 0, 0, 4, 3);
}

private static void combination(int[] target, int index, int depth, int n, int r) {
    // r개를 완성했다면 출력
    if(r == 0) {
        for (int num : target) {
            System.out.print(num + " ");
        }
        System.out.println();
        return;
    }

    // 현재 인덱스가 배열을 넘어서는 경우
    if (depth == n) {
    	return;
    }
	
    // 현재 인덱스를 target에 추가
    target[index] = array[depth];
    // target의 다음 인덱스에 현재 숫자를 한 번 더 넣거나,
    combination(target, index + 1, depth, n, r - 1);
    // 현재 인덱스에 다음 숫자를 넣도록 한다.
    combination(target, index, depth + 1, n, r);
}

---

본 포스트에서 조합과 중복조합에 대해 정리했습니다.

다음부터는 문제가 나오더라도 술술 작성할 수 있도록 새깁시다.

 

참고

https://bcp0109.tistory.com/15?category=848939 

조합 Combination (Java)