C++ 순열(Permutation)과 조합(Combination)

순서와 상관이 있다면 → 순열

순서와 상관이 없다면 → 조합

1. 순열(Permutation)이란?

순열은 순서를 고려하여 주어진 요소 중에서 몇 개를 선택해 나열하는 경우의 수를 말합니다.

EX) [A, B , C] 중에서 두 개를 선택하는 순열 → AB, AC, BA, BC, CA, CB(총 6가지)

2. 조합(Combination)이란?

조합은 순서를 고려하지 않고 주어진 요소 중에서 몇 개를 선택하는 경우의 수를 말합니다.

EX) [A, B, C] 중에서 두 개를 선택하는 조합 → AB, AC, BC (총 3가지)

순열과 조합을 C++로 구현하기

1.C++의 next_permutation을 이용한 순열 구현

<algorithm> 헤더에서 제공하는 next_permutation을 사용하면 간단하게 순열을 구현할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	vector<int> nums = {1, 2, 3};
	
	do {
		for (int num: nums) {
			cout << num << " ";
		}
		cout << endl;
	} while (next_permutation(nums.begin(), nums.end()));
}

// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 1 2 
// 3 2 1

2. 재귀를 이용한 조합 구현

재귀를 활용해 조합을 구할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n = 5; 
int k = 3; 
int a[5] = {1, 2, 3, 4, 5};
void print(vector<int> b) {
	for(int i : b) cout << i << " ";
	cout << endl;
}
void combi(int start, vector<int> &b) {
	if (b.size() == k) {
		print(b);
		return;
	}
	for (int i = start + 1; i < n; i++) {
		b.push_back(i);
		combi(i, b);
		b.pop_back();
	}
	return;
}

int main() {
	vector<int> b;
	combi(-1, b);
}

// 0 1 2
// 0 1 3
// 0 1 4
// 0 2 3
// 0 2 4
// 0 3 4
// 1 2 3
// 1 2 4
// 1 3 4
// 2 3 4