반응형
조합
순열과 다르게 순서는 상관없이 주어진 n개 중에서 r개을 뽑아서 나열하는 것
for문
최대 3개까지 뽑는경우에는 효율적이나 그 이상일 경우 재귀함수를 통해 구현하는 것이 효율적
#include<iostream>
#include<vector>
using namespace std;
vector<int> v;
int n = 5;
int main() {
for (int i = 0; i < n; i++) {
v.push_back(i + 1);
}
//5개중 3개를 뽑는 경우
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
cout << v[i] << ' ' << v[j] << ' ' << v[k] << '\n';
}
}
}
cout << '\n';
//5개중 2개를 뽑는 경우
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
cout << v[i] << ' ' << v[j] << '\n';
}
}
return 0;
}
//출력
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
재귀함수
재귀함수로 조합을 하는 경우에 탈출조건 : 뽑는 개수와 벡터안의 요소의 개수와 같을 때
처음에 combination(-1,v)로 시작하는 이유는 벡터가 뽑는 개수와 동일한 개수를 가졌을 때 pop_back()을 통해 마지막 요소를 버리고 이미 저장된 start값에서 +1을 한 요소부터 다시 저장하기 위해서이다. 만약 combination(0,v)로 한다면 start의 값이 배열 a에서 인덱스가 증가 하지 않기 때문에 중복된 값을 뽑아서 v에 저장하게 된다.
그러므로 -1부터 뽑은 요소의 인덱스를 임의로 증가시켜주기 위해서 -1로 설정후 for문에서 +1을 하는 방식을 사용한 것이다.
#include<iostream>
#include<vector>
using namespace std;
vector<int> a = { 2,3,4,5,6 };
int n = a.size();
int r = 3;
void combination(int start, vector<int> v) {
if (v.size() == r) {
for (auto ele : v) {
cout << ele << ' ';
}
cout << '\n';
}
for (int i = start + 1; i < n; i++) {
v.push_back(a[i]);
combination(i, v);
v.pop_back();
}
}
int main() {
vector<int> v;
combination(-1, v);
return 0;
}
//출력
2 3 4
2 3 5
2 3 6
2 4 5
2 4 6
2 5 6
3 4 5
3 4 6
3 5 6
4 5 6
반응형
'Language > C++' 카테고리의 다른 글
(C++)all_of,any_of,none_of (0) | 2023.05.18 |
---|---|
(C++)DFS,BFS (0) | 2023.02.22 |
(C++)순열 (0) | 2023.02.21 |
(C++)배열의 최댓값,최솟값-max_element,min_element (0) | 2023.02.20 |
(C++)배열 초기화-memset,fill (0) | 2023.02.08 |