[C++/Algorithm] 순열과 조합 구현하기

이번 포스팅에서는 C++로 순열과 조합을 구현해보려 한다.

 

1. 순열

순열은 '순서'의 개념이 존재하는 조합이다

 

가령 [1, 2, 3] 중 3개의 원소로 만들 수 있는 모든 순열의 집합은

[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 이렇게 6개의 순열이 나올 수 있고, 간단하게 3!로 그 수를 구할 수 있다.

 

컴퓨터로 순열을 구현하는 방법에는 몇 가지가 있는데, 가장 기본적으로 DFS 방식, 즉 재귀적으로 방문처리를 이용하여 순열을 구할 수 있다.

 

// Permutation DFS로 구현

#include <bits/stdc++.h>

using namespace std;

void Permutation(int visited[3], vector<int> & vec, vector<int>& res, int cnt) {
	if (cnt == vec.size()) {
		for (auto a : res) {
			cout << a << " ";
		}
		cout << endl;
		return;
	}
	
	for (int i = 0; i < vec.size(); i++) {
		if(visited[i] == 1)	continue;

		visited[i] = 1;
		res[cnt] = vec[i];
		Permutation(visited, vec, res, cnt + 1);
		visited[i] = 0;
	}
}
int main(void){	
	int a[3] = {1, 2, 3};
	
	vector<int> vec;
	vector<int> res(3);
	
	for (int i = 0; i < 3; i++) {
		vec.push_back(a[i]);
	}
	int visited[3];
	memset(visited, sizeof(visited), 0);

	Permutation(visited, vec, res, 0);
	
	return 0;
}

 

알고리즘의 로직을 간단하게 살펴보면, 

 

[1, 2, 3]의 벡터(집합)를 Permutation 함수에 입력하게 되면 

 

* cnt = 0으로 출발

* 첫 for문 -> 방문 처리되어있는 인덱스 없음 -> 처음 인덱스부터 선택 -> 1 선택

* 1 선택 -> 1 방문 처리 -> cnt = 1 -> 다음 Permutation 호출

* 1은 방문 처리 되어있으므로 그다음 2 선택 -> cnt = 2 -> 다음 Permutation 호출... (1)

* 방문처리 되어있지 않은 3 선택 -> cnt = 3 -> 다음 Permutation 호출... (2)

* cnt = 3이므로 출력 후 반환 (1, 2, 3)

* (2) 로 반환. 하지만 (2)에서 추가적으로 깊이 들어갈 원소가 없으므로 다시 반환

* (1) 로 반환.  여기서 2를 선택하지 않고 3을 선택 -> cnt = 2 -> 다음 Permutation 호출

* 방문 처리되어있지 않은 2 선택 -> cnt = 3 -> 다음 Permutation 호출

* cnt = 3이므로 출력 후 반환 (1, 3, 2)

 

...

 

위와 같이 재귀적으로 DFS의 로직에 따라 순열을 구할 수 있다.

 

다음과 같은 방법으로 구현할 수도 있다.

 

// Permutation 구현 방법 2

#include <bits/stdc++.h>

using namespace std;

void Permutation(vector<int> & vec, int n, int r, int depth) {
	
	if(depth == r) {
		for (auto a : vec) {
			cout << a << " ";
		}
		cout << endl;
		return;
	}
	
	for (int i = depth; i < vec.size(); i++) {
		swap(vec[i], vec[depth]);
		Permutation(vec, n, r, depth + 1);
		swap(vec[i], vec[depth]);
	}
	
}
int main(void){	
	int a[3] = {1, 2, 3};
	
	vector<int> vec;
	vector<int> res(3);
	
	for (int i = 0; i < 3; i++) {
		vec.push_back(a[i]);
	}
	
	const int n = 3;
	const int r = 3;
	
	Permutation(vec, n, r, 0);
	
	return 0;
}

 

위 코드는 첫 번째 방법보다 직관적으로 이해가 어렵기 때문에 그림의 도움을 받아 이해해보자

 

 

그림과 같이 처음 1, 2, 3에서 [0, 0], [0, 1], [0, 2] 이렇게 swap이 일어난다. 

그러면 그림과 같이

 

[1, 2, 3] , [2, 1, 3], [3, 2, 1] 세 가지 조합이 일어나게 되고, 그다음 Permutation 함수에서 depth=1이기 때문에 1번째 인덱스부터 swap을 발생시키면 각각 두 가지 조합이 더 생겨나게 된다.

 

마지막으로 C++/STL에서 제공하는 next_permutation 함수를 사용하는 방법이 있고, 아마 대부분의 코딩테스트 문제에서 순열을 사용할 일이 있으면 이 방법을 이용할 듯하다.

(next_permutation은 오름차순 정렬이 되어있을 때 사용 가능하다. 만약 내림차순 정렬이 되어 있다면 prev_permutation을 사용하도록 한다)

 

// next_permutation 이용 

#include <bits/stdc++.h>

using namespace std;

int main(void){	
	int a[3] = {1, 2, 3};
	
	vector<int> vec;
	vector<int> res(3);
	
	for (int i = 0; i < 3; i++) {
		vec.push_back(a[i]);
	}

	do {
		for (auto a : vec) {
			cout << a << " ";
		}
		cout << endl;
	}while(next_permutation(vec.begin(), vec.end()));
	
	return 0;
}

 

보통 위와 같이 do while문을 활용하여 구현하는 것이 일반적이며, vector iterator의 시작점, 끝점을 parameter로 전달하면 위 두 코드와 같은 결과를 출력해 준다.

 

2. 조합

위의 순열에서 순서의 개념을 뺀 집합을 조합이라 한다.

 

즉 순열에서는 [1, 2, 3]과 [1, 3, 2], [3, 1, 2]... 모두 다른 순열이지만, 조합에서는 순서에 관계없이 1, 2, 3은 같은 조합 구성으로 본다.

 

순열에 비해 간단한 로직이기 때문에 만약에 3개 정도를 뽑는다 치면 간단하게 for문 중첩으로도 구현할 수 있다.

 

// for문 중첩을 활용한 조합 구현 

#include <bits/stdc++.h>

using namespace std;

int main(void){	
	int a[6] = {1, 2, 3, 4, 5, 6};
	
	vector<int> vec;
	
	for (int i = 0; i < 6; i++) {
		vec.push_back(a[i]);
	}
	
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < i; j++) {
			for (int k = 0; k < j; k++) {
				cout << vec[i] << " " << vec[j] << " " << vec[k] << endl;
			}
		}
	}
	return 0;
}

 

위와 같이 간단하게 구현해볼 수 있다.

 

하지만 조금 복잡한 조합을 구할 때는 for문 중첩으로는 한계가 있기 때문에 이를 다시 재귀 함수로 구현해보면,

 

// 재귀를 활용한 조합 구현 

#include <bits/stdc++.h>

using namespace std;

void Combination(vector<int>& vec, vector<int>& res, int start) {
	
	if(res.size() == 3) {
		for (auto a : res) {
			cout << a << " ";
		}
		cout << endl;
	}
	
	for (int i = start; i < vec.size(); i++) {
		res.push_back(vec[i]);
		Combination(vec, res, i + 1);
		res.pop_back();
	}
}
int main(void){	
	int a[5] = {1, 2, 3, 4, 5};
	
	vector<int> vec;
	vector<int> res;
	
	for (int i = 0; i < 5; i++) {
		vec.push_back(a[i]);
	}
	
	Combination(vec, res, 0);
	return 0;
}

 

위 코드와 같이 순서의 개념이 없는 조합에서는 이미 선택된 원소 다음 원소부터 loop를 재귀적으로 순회하며 추가를 해주면 된다.

 

마지막으로 next_permutation을 활용하여 조합을 구현할 수 있다.

 

가령 vector가 [1, 2, 3, 4, 5]로 있다 하면,

 

visited라는 배열을 [0, 0, 1, 1, 1]으로 설정하고, visited라는 배열을 next_permutation의 인자로 전달한다. 그렇게 되면

 

next_permutation이라는 함수는 위의 visited 배열로 만들 수 있는 경우의 수를 모두 만들어 주게 되고,

 

visited [index] = 1인 원소만 출력을 해주면 우리가 원하는 결과를 얻을 수 있다.

 

주의할 점은 next_permutation은 오름차순 정렬이 되어 있어야 하기 때문에 false부터 채우고, 우리가 조합을 원하는 수를 뒤에서부터 true로 채워주면 된다.

 

// next_permutation 이용 

#include <bits/stdc++.h>

using namespace std;

int main(void){	
	int a[5] = {1, 2, 3, 4, 5};
	
	vector<int> vec;
	
	for (int i = 0; i < 5; i++) {
		vec.push_back(a[i]);
	}

	vector<bool> visited(5, true);
	
	for (int i = 0; i < vec.size() - 3; i++) visited[i] = false;
	do {
		for (int i = 0; i < vec.size(); i++) {
			if (visited[i])	cout << vec[i] << " ";
		}
		cout << endl;
	}while(next_permutation(visited.begin(), visited.end()));
	
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.