C++ 조합(Combination) - next_permutation

 

 

 

---

1. 조합(Combination)

 

조합(Combination)이란 n개의 원소를 갖는 집합에서 m(n 이하의 자연수)개를 선택하여 만드는 부분집합들이다.

 

 

C++에서는 algorithm 라이브러리의 next_permutation을 사용하면 이를 쉽게 구할 수 있다.

 

 

 

 

본래 next_permutation은 순열(Permutation)을  구할 때 사용하였었다.

 

C++ 순열(Permutation) - next_permutation

 

이런 순열(Permutation)의 특성을 이용하면 조합(Combination) 또한 구할 수 있다.

 

 

 

---

2. 코 드

환경 : Visual studio 2019

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

int main() {
	string s = "12345";
	int len = s.size();

	for (int i = 1; i <= len; i++) {
		vector<bool> v(len - i, false);
		v.insert(v.end(), i, true);
		cout << "=============== " << i << "개 ===============\n";
		do {
			string temp = "";
			for (int k = 0; k < len; k++) {
				if (v[k]) temp += s[k];
			}
			cout << temp << "\n";
		} while (next_permutation(v.begin(), v.end()));
		cout << "===================================\n";
	}

	return 0;
}

 

 

결과

 

- 해당 예시에서는 간단하게 문자열을 사용하였다. 이를 vector로 바꾸거나한다면 집합에서 조합을 구하는 것처럼 할 수 있다.

 

 

- vector v는 집합(여기서는 s)의 크기만큼을 갖으며,  i는 선택할 원소의 개수이다.

 

따라서 s의 길이는 5이므로 1~5까지 for루프를 돌면서 원소를 1개 선택하는 경우, 2개 선택하는 경우, ... ,5개 선택하는 겨우를 각각 구할 수 있는 것이다.

 

i  : v

1 : false, false, false, false, true   =>   5개 중 1개 선택하는 경우

2 : false, false, false, true, true  =>   5개 중 2개 선택하는 경우

3 : false, false,true, true, true=>   5개 중 3개 선택하는 경우

4 : false, true, true, true, true  =>   5개 중 4개 선택하는 경우

5 : true, true, true, true, true  =>   5개 중 5개 선택하는 경우

 

 

 

- do~while 문을 이용하여 next_permutation을 사용한다.

 

next_permutation에 의하여 v의 순서가 바뀌며 v의 원소 중 true일 경우 같은 인덱스의 위치하는 문자열 s의 문자를 합치면 조합을 구해낼 수 있다.

 

 

 

 

 

---

3. 참 조

 

[STL] Vector 생성, 삽입, 삭제 등 사용법

 

 

 

next_permutation - C++ Reference