STL을 이용한 조합과 순열 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void combination(vector<int>& list, int n, int r) {
	vector<int> selection;
	for (int i = 0; i < r; i++) selection.push_back(1);
	for (int i = 0; i < n - r; i++) selection.push_back(0);
	do {
		for (int i = 0; i < list.size(); i++) {
			if (selection[i] == 1) cout << list[i] << ' ';
		}
		cout << "\n";
	} while (prev_permutation(selection.begin(), selection.end()));
}

void permutation(vector<int> list, int n, int r) {
	do {
		for (int i = 0; i < r; ++i) cout << list[i] << ' ';
		cout << "\n";
	} while (next_permutation(list.begin(), list.end()));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> list{ 4,2,1,3 };

	// 조합은 정렬되지 않은 상태로 입력해도 됨
	combination(list, 4, 2); 
	cout << endl;

	// 순열은 오름차순으로 정렬된 리스트를 입력해야 함
	sort(list.begin(),list.end()); 
	permutation(list, 4, 2);

	return 0;
}

// 조합 출력 결과
4 2
4 1
4 3
2 1
2 3
1 3

// 순열 출력 결과
1 2
1 2
1 3
1 3
1 4
1 4
2 1
2 1
2 3
2 3
2 4
2 4
3 1
3 1
3 2
3 2
3 4
3 4
4 1
4 1
4 2
4 2
4 3
4 3

 

---

조합 알고리즘은 리스트가 정렬되어 있지 않아도 되므로,

다양한 자료형에 적용할 수 있다.

pair<int, int> 타입으로 조합을 하면, 다음과 같다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> int_pair;

void combination(vector<int_pair>& list, int n, int r) {
	vector<int> selection;
	for (int i = 0; i < r; i++) selection.push_back(1);
	for (int i = 0; i < n - r; i++) selection.push_back(0);
	do {
		for (int i = 0; i < list.size(); i++) {
			if (selection[i] == 1) {
				cout << "(" << list[i].first << ", " << list[i].second << ") ";
			}
		}
		cout << "\n";
	} while (prev_permutation(selection.begin(), selection.end()));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int_pair> list{ make_pair(1,2), make_pair(3,2), make_pair(0,0), make_pair(2,1)};
	combination(list, 4, 2);

	return 0;
}

(1, 2) (3, 2)
(1, 2) (0, 0)
(1, 2) (2, 1)
(3, 2) (0, 0)
(3, 2) (2, 1)
(0, 0) (2, 1)

 

혹시 성능을 세밀하게 컨트롤해야 한다면, 다음과 같은 코드로 인덱스의 조합을 통해 똑같은 결과를 만들어 낼 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef pair<int, int> int_pair;

vector<int_pair> list{ make_pair(1,2), make_pair(3,2), make_pair(0,0), make_pair(2,1) };

void combination(vector<int>& index, int n, int r) {
	vector<int> selection;
	for (int i = 0; i < r; i++) selection.push_back(1);
	for (int i = 0; i < n - r; i++) selection.push_back(0);
	do {
		for (int i = 0; i < index.size(); i++) {
			if (selection[i] == 1) {
				cout << "(" << list[index[i]].first << ", " << list[index[i]].second << ") ";
			}
		}
		cout << "\n";
	} while (prev_permutation(selection.begin(), selection.end()));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	vector<int> index{ 0,1,2,3 };
	combination(index, 4, 2);

	return 0;
}

(1, 2) (3, 2)
(1, 2) (0, 0)
(1, 2) (2, 1)
(3, 2) (0, 0)
(3, 2) (2, 1)
(0, 0) (2, 1)

 

---

순열과 조합은 위와 같이 STL의 prev_permutation이나 next_permutation을 통해 구현할 수도 있지만

DFS를 통해서도 구현할 수 있다고 한다.

 

출처1 : codemcd.github.io/algorithm/Algorithm-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9/ 

출처2 : mjmjmj98.tistory.com/38