[Algorithm] C++에서 next_permutation을 이용해 조합(Combination) 구하기
C++의 next_permutation 함수를 이용해서 조합을 만들어보자
환경 및 선수조건
next_permutation 함수
기본 사용법
위 링크를 통해서 더 자세하게 볼 수 있지만 간단하게나마 정리하고 갑니다.
example.cpp
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main (){
vector<int> v;
// 1부터 4까지 대입
for(int i=0; i<4 ;i++){
v.push_back(i+1);
}
// 정렬
sort(v.begin(), v.end());
//순열
do{
// 출력
for(int i=0; i<v.size(); i++){
printf("%d ", v[i]);
}
printf("\n");
}while(next_permutation(v.begin(), v.end()));
return 0;
}
중복이 있는 원소들의 경우
중복이 있는 원소의 경우 중복인 경우를 제외하고 순열을 만들어줍니다. 즉, 예를 들어서 0 1 1이 있다면 아래와 같은 경우만 순열을 출력해줍니다.
0 1 1
1 0 1
1 1 0
example.cpp
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main (){
vector<int> v;
// 0 1 1 대입
v.push_back(0);
v.push_back(1);
v.push_back(1);
// 정렬
sort(v.begin(), v.end());
//순열
do{
// 출력
for(int i=0; i<v.size(); i++){
printf("%d ", v[i]);
}
printf("\n");
}while(next_permutation(v.begin(), v.end()));
return 0;
}
next_permutation을 이용해 조합(Combinataion) 구하기
원리
전체 n개의 원소들 중에서 k개를 뽑는 조합(=nCk)을 구한다면 n개의 벡터 원소에 1을 k개 0을 나머지인 n-k개 집어넣어서 순열을 돌리고 1에 해당하는 인덱스만 가져오면 된다.
코드
1부터 6까지의 수 중에서 4개를 뽑아서 조합을 만들어보자.
example.cpp
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main (){
// 1부터 6까지 담을 벡터
vector<int> n;
// 1부터 6까지 생성
for(int i=0; i<6; i++){
n.push_back(i+1);
}
// 0과1을 저장 할 벡터 생성
vector<int> ind;
// k=4, 4개를 뽑으니까
int k = 4;
// k개의 1 추가
for(int i=0; i<k; i++){
ind.push_back(1);
}
// 2개(6개-2개)의 0 추가
for(int i=0; i<n.size()-k; i++){
ind.push_back(0);
}
// 정렬
sort(ind.begin(), ind.end());
//순열
do{
// 출력
for(int i=0; i<ind.size(); i++){
if(ind[i] == 1){
printf("%d ", n[i]);
}
}
printf("\n");
}while(next_permutation(ind.begin(), ind.end()));
return 0;
}
구현 결과
3 4 5 6
2 4 5 6
2 3 5 6
...
1 2 3 6
1 2 3 5
1 2 3 4