[C++] next_permutation을 사용한 조합 만들기

순열을 사용하여 조합을 만들어내는 방법입니다.


로직을 설명하면 vector <int>를 2개를 선언하고

하나는 원소를 삽입하는 vector <int> list를

또 다른 하나는 순서 제어를 위해서

next_permutation을 사용할 vector <int> idx를 만듭니다.


이어서

몇 개의 원소를 뽑을지 결정하는 변수 r 만큼

idx에 1을

list의 크기 (n이라고 하겠습니다) - r 만큼

idx에 0을 넣습니다.


그 뒤로 idx를 next_permutation을 사용하여 반복하여

idx의 원소가 1일 때마다 list의 원소를 출력해주면 됩니다.


저는 내림차순으로 출력하기 위해서 desc라는 함수를 따로 작성하였습니다.

소스코드

// Combination 
// using STL's next_permutation
 
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
bool desc(int a, int b){
    return a > b;
}
 
int main(){
    int n;
    int r;
    vector<int> idx;
    vector<int> list;
    
    cout << "몇 개의 원소를 가진 배열입니까?" << '\n';
    cin >> n;
    cout << "원소를 삽입하세요" << '\n';
    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        list.push_back(tmp);
    }
    
    cout << "몇 개의 원소를 뽑아냅니까?" << '\n';
    cin >> r;
    for(int i = 0; i < r; i++)
        idx.push_back(1);
    for(int i = 0; i < n-r; i++)
        idx.push_back(0);
    sort(idx.begin(), idx.end(),desc);
    
    do{
        for(int i = 0; i < n; i++){
            if(idx[i] == 1)
                cout << list[i];
        }
        cout << '\n';
    }while(next_permutation(idx.begin(), idx.end(),desc));
    
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.