permutation, combination 구현 C++

회사에서 치는 시험에 구글링이 안 되서 짬짬이 알고리즘들 개념을 다시 정리하고자 한다.

 

1. permutation (순열)

간단히 {0,1,2,3,4} 배열에서 5P3 을 구한다고 하면 {0,1,2} ~ {4,3,2} 까지가 계산된다. 

이를 계산하기 위한 방법은 다음과 같다.

- 전체 배열에서 현재 체킹하고 있는 인덱스가 방문했었다면 다음 인덱스로 넘어간다.

- 방문 안 했었다면, 해당 값을 추가하고, 처음 루프부터 다시 이를 진행한다. (재귀)

- 재귀적으로 진행하면서 추가된 값이 총 r 개를 만족하면 결과에 추가한다.

- 재귀가 끝나면 체킹했던 인덱스 방문을 해제한다.

 

{0,1,2,3,4} 로 되어 있는 배열에 대해 살펴 보면, 

- 0번째 값인 0이 현재 체크가 되어 있지 않으므로 0을 추가 ... 2까지 추가

- {0,1,2} 가 결과에 추가

- 2의 방문을 해제하고, 그 다음 인덱스인 3을 추가, 3을 해제하고 4를 추가

- {0,1,3}, {0,1,4} 결과에 추가

- 1의 방문을 해제하고, 그 다음 인덱스인 2를 추가, 처음부터 체킹하므로 0은 현재 체킹, 1 체킹 해제되었으므로 1을 방문

- {0,2,1} 결과에 추가

 

이런 식으로 재귀를 바탕으로 permutation을 구할 수 있다.

 

2. combination (조합)

combination은 permutation보다 간단하다. permutation 에서는 순서가 영향을 끼치지만, combination은 순서가 상관없으므로, 방문 여부와 관계없이 재귀를 진행하면 된다. 그리고 현재 체킹 중인 인덱스 다음 인덱스부터 재귀를 진행하면 된다. 

 

{0,1,2,3,4} 로 되어 있는 배열에 대해 살펴 보면, 

- 0번째 인덱스부터 체킹하므로 0을 추가, ... 2까지 추가

- {0,1,2} 결과에 추가, 현재까지 체킹된 인덱스는 2

- 재귀 종료 후 2번째 위치에 다음 값인 3을 넣음

- {0,1,3} 결과에 추가, 마찬가지로 {0,1,4} 결과에 추가

- 재귀 종류 후 현재 체킹 중인 인덱스는 1

- 그 다음 인덱스 값인 2를 1의 위치에 추가 {0,2} 생성

- 그 다음 인덱스 값인 3을 추가 {0,2,3} 생성 후 결과에 추가 

 

(코드를 보면 쉽게 이해가 된다.)

#include <iostream>
#include <vector>

using namespace std;

// permutation 원리 
// A B C D 에서 4P3
// A B C -> A B D
// 위처럼 진행되야 하므로
// A B C 탐색 시 
// C 체킹 후 3개 다 만족했으므로 결과에 추가 
// 그리고 C 체킹한 부분 해제 후 D 체킹으로 추가 
// 이를 반복  
void permutation(vector<bool> &visited, vector<int> &vec, vector<int> &perm, vector<vector<int>> &result, int depth, int n, int r)
{
	// nPr
	if(depth == r) {
		result.push_back(perm);
		return;
	}
	
	for(int i = 0; i < n; i++) {
		if(visited[i])
			continue;
		
		visited[i] = true;
		perm[depth] = vec[i];
		permutation(visited, vec, perm, result, depth+1, n, r);
		visited[i] = false;
	}
}

// combination 원리 
// A B C D 에서 4C3
// A B C, B C A 는 같은 케이스 
// 따라서 permutation에서 visited로 방문 체킹하고 해제하는 부분이 없어야 함
// 그리고 loop에서 현재 체킹 중인 index가 몇 번째인지를 체크해줌 
// permutation의 경우, A B C 이후에 B A C 가 가능한 것은 A 방문 해제 및 loop 를 처음부터 돌기 때문
// 따라서 permutation 구현한 것에서 "visited 제거", "loop는 현재 체킹 중인 인덱스 다음부터"를 추가하면됨
void combination(vector<int> &vec, vector<int> &comb, vector<vector<int>> &result, int idx, int depth, int n, int r)
{
	// nCr
	if(depth == r) {
		result.push_back(comb);
		return;
	} 
	for(int i = idx; i < n; i++) {
		comb[depth] = vec[i];
		combination(vec, comb, result, i+1, depth+1, n, r);
	}
}

// nPr, nCr 값만 필요한 경우, 공식 이용 및 dp 적용 
// nPr = n*(n-1)*...*(n-r+1)
// nCr = nPr / r! = n-1 C r-1 + n-1 C r 

void print_result(vector<vector<int>> &result)
{
	for(auto res : result) {
		for(auto val : res) {
			cout << val << " ";
		}
		cout << '\t';
	}
	cout << "\n # of result : " << result.size() << '\n';
}

int main()
{
	int n = 5;
	int r = 3;
	
	vector<bool> visited(n, false);
	vector<int> vec(n);
	for(int i = 0; i < 5; i++) {
		vec[i] = i;
	}
	
	vector<int> perm(r);
	vector<vector<int>> result;
	int depth = 0;
	
	permutation(visited, vec, perm, result, depth, n, r);
	
	cout << "Permutations 5P3 on {0,1,2,3,4} : \n";
	
	print_result(result);
	
	cout << "\n=====================\n";
	
	vector<int> comb(r);
	result.clear();
	int idx = 0;
	
	combination(vec, comb, result, idx, depth, n, r);
	
	cout << "Combinations 5C3 on {0,1,2,3,4} : \n";
	
	print_result(result);
}

 

결과