[Java]중복 조합(Combination with repetition)

중복 조합을 완벽하게 이해하기 위해서는 순열, 중복 순열, 조합 세 가지를 모두 정확히 이해하고 공부하는 것이 좋다

sskl660.tistory.com/48?category=879763

[Java] 순열(Permutation)

 

sskl660.tistory.com/49?category=879763

[Java] 중복 순열(Permutation with repetition)

sskl660.tistory.com/50?category=879763

[Java] 조합(Combination)

 

*중복 조합(Combination with repetition)

-> 중복 조합이란, 임의의 집합을 순서가 없이 선택하는데 일반 조합과 다르게 집합의 원소를 중복해서 선택할 수 있는 차이가 존재한다.

Ex) 이를 테면 집합 {1, 2, 3}중 2개의 원소를 선택한 중복 조합의 결과는 {11, 12, 13, 22, 23, 33} 총 6가지 경우의 수가 나온다.

 

※ 중복 조합의 경우의 수(이 부분은 수학적인 내용이 많으니 경우의 수를 굳이 이해하고 싶지 않다면 스킵하셔도 무관합니다).

-> 중복 조합의 경우의 수는 조합에서 경우의 수를 구하는 것과 동일하게 생각하면 안된다! 조합에서 경우의 수를 구하는 것은 순열로 뽑은 수에서 '순서를 제거하는 것'이라고 하였다. 하지만 중복 조합에서는, 순서를 제거하는 경우 원치않는 경우의 수까지 제거해버리기 때문에 문제가 발생한다.

.

 조합의 경우의 수를 이해하기 위해 위의 그림을 참고하면, {1, 2, 3}에서 2개를 선택하는 순열은 각 선택에 대하여, 순서가 존재함을 알 수 있다. 이를 테면, 12라는 선택은 순서를 부여하면 21이라는 새로운 경우를 도출할 수 있다. 마찬가지로 13은 순서를 부여하면 31이라는 새로운 경우를 도출할 수 있다. 따라서 조합에서는 이러한 '순서'의 개념을 제거한 것이다.

 마찬가지로 {1, 2, 3}에서 3개를 선택하는 순열은 123이라는 선택은 순서를 부여하면 132, 213, 231, 312, 321이라는 5가지 경우를 더 도출할 수 있다. 마찬가지로 조합에서는 이 '순서'의 개념을 제거한 것 뿐이다.

 

-> 중복 조합의 경우의 수는 이와 다르다. 이를 테면 {1, 2, 3}에서 2개를 선택하는 중복 순열과 중복 조합을 그림을 통해 확인해보면 다음과 같다.

 중복 순열에서는 '순서'라는 개념을 제거할 수 없다. 위의 예시를 그대로 활용하여 이해해보면, 12라는 선택은 순서를 부여하면 21이라는 새로운 경우의 수를 도출할 수 있지만, 11이라는 선택은 순서를 부여하더라도 11이라는 똑같은 경우를 도출하기 때문에 의미가 없다. 따라서 무턱대고 모든 경우에 대하여 동등하게 순서를 제거해버린다면 문제가 발생할 수 밖에 없기 때문에, 조합에서 경우의 수를 구하는 것 처럼 생각하면 안된다.

 

-> 그렇다면 중복 조합의 경우의 수는 어떻게 구할 수 있을까? 먼저 중복 조합의 경우의 수는 다음과 같이 표현하고, 다음 공식을 활용하여 구할 수 있다.

중복 조합 공식

 특히 빨간 부분을 집중해서 보면서 다음 내용들을 이해해보도록 하자. 이를 테면, {1, 2, 3}의 집합에서 중복 조합을 고르는 방식은 다른 방법으로 치환하여 생각해볼 수 있다.

 {1, 2, 3}이라는 집합에서 다음과 같이 1, 2, 3을 넣을 수 있는 영역을 각각 막대기를 통해서 구분한뒤, 2개를 선택하는 경우의 수를 생각해보자.

 막대기로 구분 된 각 영역에, 중복을 허용하여 집합에서 숫자를 선택한 뒤 영역에 넣는 경우의 수를 생각해보면 위와 같은 경우를 생각할 수 있다. 이를 일반화하여 생각하면, n개의 원소를 가진 집합에서 r개를 선택하는 경우, 구분하는 영역을 n - 1개로 분할하는 막대기의 개수와 선택하고자하는 숫자 r개 중 숫자 r개를 선택하는 조합으로 바꾸어 생각할 수 있다!(반대로, 숫자와 막대기 중 막대기를 둘 칸을 선택하는 경우로 바꾸어 생각해도 된다. nCr = nCn-r이므로, 두 가지 중 어떤 선택을 해도 상관이 없다. 중요한 것은, 선택해야하는 숫자와 막대기의 개수는 이미 정해져 있으므로(n - 1 + r칸), 그 칸 중 숫자를 어떤 칸에 넣을 것인지 혹은 막대기를 어떤 칸에 넣을 것인지를 고민하는 느낌을 이해하면 된다).

 

*구현(Java)

-> 중복 조합은 조합에서 중복 선택이 가능하도록 조치만 취해주면 되기 때문에 구현은 간단하다.

※ 중복 조합 알고리즘

1. 대상 집합을 순회하며 숫자를 하나 선택하는 것을 아래와 같이 반복한다.

(1) 집합을 순회하며 탐색을 하되, 입력된 인덱스부터 탐색한다.

(2) 수를 선택했다면, 해당 인덱스와 같은 인덱스를 다음 재귀 함수에 넘겨준다.

2. 선택된 숫자가 r개가 된다면, 재귀를 종료한다.

 

-> 예를 들어, 1부터 3까지의 자연수 3개 중 2개를 선택한 중복 조합은 다음과 같이 구현할 수 있다.

package cases;

import java.util.Arrays;

public class Combination_with_repetition {
	// 선택하고자 하는 대상 집합.
	static int[] target = new int[] { 1, 2, 3 };
	// 대상 숫자를 담아둘 배열.
	static int[] result = new int[2];

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

	// 조합 메서드(cnt는 선택 횟수, idx는 다음 대상을 선택할때 집합에서 탐색을 시작할 인덱스).
	private static void combination(int cnt, int idx) {
		// 2개를 선택했으므로, 결과를 출력하고 재귀를 종료한다.
		if (cnt == 2) {
			System.out.println(Arrays.toString(result));
			return;
		}
		// 대상 집합을 주어진 인덱스부터 순회하며 숫자를 하나 선택한다.
		for (int i = idx; i < 3; i++) {
			// 숫자를 담는다.
			result[cnt] = target[i];
			// 자신을 재귀 호출한다(자신의 수는 중복 선택이 가능하므로, 인덱스를 그대로 넘겨준다).
			combination(cnt + 1, i);
		}
	}
}