반응형
1. 순열 구현
int main (){
vector<int> v;
// 1부터 4까지 대입
for(int i=0; i<4 ;i++){
v.push_back(i+1);
}
// 정렬
sort(v.begin(), v.end());
//순열 (nPr)
do{
// v[i]가 실제로 순열로 처리되는 부분
for(int i=0; i<r; i++){
printf("%d ", v[i]);
}
printf("\n");
}while(next_permutation(v.begin(), v.end()));
return 0;
}
*중복이 있는 경우 자동으로 중복을 제외하여 구현됨
2. nCk 조합 구현
k개의 1과 n-k개의 0을 순열로 구현하여 해당 인덱스의 값을 출력하는 방식으로 구현
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;
}
출처 : https://twpower.github.io/90-combination-by-using-next_permutation
반응형