[Java]조합(Combination)

조합은 기본적으로 순열을 이해하고 있어야 이해하기 더 수월하다.

sskl660.tistory.com/48

[Java] 순열(Permutation)

 

*조합(Combination)

-> 조합이란, 임의의 집합을 순서가 없이 선택하는 것을 말한다.

Ex) 이를 테면 집합 {1, 2, 3}중 2개의 원소를 선택한 조합을 구하시오라고 하면, 결과는 {12, 13, 23} 총 3가지의 경우의 수가 나온다.

조합 경우의 수

※ 조합이 총 3가지가 나오는 이유는, 위의 예시에서 선택한 2가지 수를 박스에 하나씩 넣는 상황을 가정해보자. 우선 3개의 숫자 중 2개의 숫자를 선택하여 나열하는 순열을 구한다. 이후, 2개의 공간에 나열된 숫자들은 '순서'를 부여 받은 상태이므로 그 '순서를 부여 받은 상태를 제거' 해준다면 조합의 경우의 수를 구할 수 있다. 즉, 2개중 2개를 선택하는 순열의 경우의 수로 나눠주면 된다.

-> 위의 조합의 경우의 수를 일반화하면, n개의 수 중 r개를 선택하는 조합은 nPr의 순열을 구하고, rPr의 순열로 나눈 값을 경우의 수로 가짐을 알 수 있다.

조합 경우의 수

*구현(Java)

-> 조합은 순열에 비해 로직을 조금 더 고민해 보아야 이해할 수 있다. 순열은 순서를 고려하였기 때문에, 재귀 호출을 하여 다음 수를 선택하는 경우 집합의 처음부터 탐색하며 다음 대상을 고려하였다. 하지만 조합은 순서를 고려하지 않기 때문에, 다음 수를 선택하는 경우 집합의 처음부터 탐색하며 다음 대상을 고려하는 경우, 이미 선택했던 경우의 수를 또 선택하는 오류가 발생한다.

조합에서 다음과 같이 다음 수를 선택할때 집합의 처음부터 탐색하면, 오류가 발생한다.

->따라서 조합은 다음과 같은 로직을 이용하면 구현할 수 있다.

※ 조합 알고리즘

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

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

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

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

 

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

import java.util.Arrays;

public class Combination {
	// 선택하고자 하는 대상 집합.
	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];
			// 자신을 재귀 호출한다(자신 이전의 수를 중복 선택하지 않도록 인덱스를 +1하여 재귀를 호출한다).
			combination(cnt + 1, i + 1);
		}
	}
}