next_permutation을 이용한 조합 구현

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

vector<int> arr;
vector<bool> check;

void set_check(int n, int r){
  for(int i=0;i<r;i++) check.push_back(true);
  for(int i=r;i<n;i++) check.push_back(false);
}

void combination(int n){
  do {
    string s="";
    for(int i=0;i<n;i++) if(check[i]) s+=(arr[i]+'0');
    cout << s << "\n";
  } while(next_permutation(check.begin(),check.end()));
}

int main() {
  arr.push_back(1);
  arr.push_back(2);
  arr.push_back(3);
  arr.push_back(4);
  arr.push_back(5);
  set_check(5,3);
  sort(check.begin(),check.end());
  combination(5);
}

 

next_permutation 함수는 배열을 순열해주는 함수이다.

일반적인 순열 순으로, 중복되지 않게 배열 요소들을 실행(반복문)마다 바꿔준다.

 

check는 순열할 때 표시할 인덱스 정보가 들어있는 벡터이다.

즉 check를 next_permutation으로 순열해서, check가 true로 되어있는 인덱스들과 동일한 arr의 인덱스들의 값을 전부 출력하면 된다.

 

set_check 함수는 초기 check벡터를 설정하는 함수이다.

만약 위 소스코드처럼 5개의 요소중 3개의 요소를 택하는 조합을 원한다면, check에 3개의 true, 2개의 false를 넣으면 된다.

 

check 벡터는 오름차 순으로 sort 해줘야 하며, 최종 순열 출력은 내림차순으로 이루어 진다.

false, false, ..... true, true

 

결과 - {1,2,3,4,5} 에서 3개의 요소를 택하는 조합