완전 탐색으로 n 개 중 r 개 고르기 (조합)

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

조합

서로 다른 n 개 원소를 가지는 집합에서 순서에 상관없이 r 개의 원소를 선택하는 경우의 수를 계산한다. 이는 n 개 원소를 가지는 집합에서 길이가 r 인 부분 집합을 고르는 문제 그리고 이항 계수와 같다.

완전 탐색으로 풀 수 있을까?

이항 계수의 공식은 n choose r = n! / (r! * (n - r)!) 이고 이는 n 개 원소 중 r 개를 고르는 조합의 가짓수와 같다. 따라서, 주어지는 n 과 r 을 통해 수행 가능성을 짐작해 볼 수 있다. 

재귀적으로 생각해보기

재귀 호출을 통해 문제를 해결하려면 동일한 형태의 작업으로 나누어 해결해야 하므로 여러개의 유사한 작업 조각으로 나눈다. r 개를 골라야 하므로 원소를 고르는 작업을 하나의 작업 조각이라 하고 원소를 하나 고른 뒤 (r - 1) 개의 원소를 고르는 작업을 재귀 호출해 해결한다.

 

하나의 작업 조각을 해결할 때는, 우선 고른 원소를 담을 배열이 필요하다. 원소를 고를 때는 선택할 수 있는 원소가 무엇인지(이미 선택한 원소는 제외해야 하므로.), 현재까지 몇 개의 원소를 선택했는지 알고 있어야 한다.

 

따라서, 재귀 함수의 인자로 원소를 저장할 배열, 선택 가능한 원소의 범위, 선택된 원소의 개수를 입력한다.

순서를 강제하기

조합은 순열과 달리 순서에 상관없이 골라진 원소들이 같다면 같은 조합이다. 예를 들어, 집합 {1, 2, 3, 4} 에서 2 개의 원소를 고르는 조합을 구할 때 {1, 2}, {2, 1} 은 같은 조합이므로 별개의 경우로 처리하면 안 된다.

 

이를 해결하기 위해 고르는 순서를 강제할 수 있다. 아직 고르지 않은 원소 중 앞에 있는 원소를 무조건 먼저 고르면 순서가 뒤바뀌지 않는다.

C++ 코드

void combination(vector<int>& picked, int n, int r){
	// 기저 사례: 더 이상 고르지 않아도 되므로 재귀 호출을 종료.
	if (r == 0) {
		printPicked(picked);
		return; 
	}

	// 아직 고른 원소가 없다면 맨 앞의 원소부터 고르고, 있다면
	// 마지막으로 고른 원소의 다음 원소부터 고른다. 
	int smallest = picked.empty() ? 0 : picked.back() + 1;
    
	for(int i = smallest; i <= n; ++i) {
		picked.push_back(i);
		combination(picked, n, r - 1);
		picked.pop_back();
	}
}

 

아래는 1 부터 n 까지의 자연수가 아닌 주어지는 배열의 원소들에 대해 순서없이 r 개를 고르는 방법이다. 반복자를 통해 배열의 앞선 인덱스의 원소부터 골라 나가며 조합을 완성한다.

 

void combination(const vector<int>& v, int r, vector<int>& picked){
	if (r == 0){
		printVector(picked);
		return;
	}
	
	// 마지막으로 고른 원소의 인덱스를 찾아 그 다음 위치부터 고른다.
	auto front = picked.empty() ? v.begin() : find(v.begin(), v.end(), picked.back()) + 1;

	for (auto it = front; it != v.end(); ++it) {
		picked.push_back(*it);
		combination(v, r - 1, picked);
		picked.pop_back();
	}
}