[c++] prev_permutation, next_permutation

중복을 제외한 순열(permutation)을 구할 때 사용하는 함수입니다.

 

수학적으로 순열이란, 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수를 말합니다.

원소를 한 줄로 세우기 때문에 원소의 조합이 같더라도 순서가 다르면 다른 방법으로 봅니다.

{1, 2, 3}원소의 모든 순열을 구하면,

{1, 2, 3} {1, 3, 2} {2, 1, 3} {2, 3, 1} {3, 1, 2} {3, 2, 1}

총 6가지가 나옵니다.

 

c++의 algorithm헤더에서 제공하는 순열을 구하는 함수는 아래와 같이 2가지 입니다.

• next_permutation
• prev_permutation

// default
bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
 
bool prev_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
// custom
bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);
                         
bool prev_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);

컨테이너의 range(first, last)를 정하고, 다음 순열이 존재하면 컨테이너의 원소를 해당 순열로 순서를 바꾸고 true를 반환합니다. 없다면 false를 반환합니다.

 

 

둘다 순열을 구하는 함수이지만, 차이점이 있습니다.

next_permutation

next_permutation은 오름차순으로 순열을 구하기 때문에 "오름차순으로 정렬된 값을 가진 컨테이너"를 사용해야 모든 순열 조합을 구할 수 있습니다. 

{3, 2, 1} 로 정렬되어 있는 배열을 사용하면, 더 이상 오름차순으로 정렬되지 않아 다음 순열은 없습니다.

vector<int> v{2, 1, 3};

sort(b.begin(), b.end());  // {1, 2, 3}

do{
	 cout << v[0] << " " << v[1] << " " << v[2] << endl;
     
}while(next_permutation(v.begin(), b.end()));

prev_permutation

prev_permutation은 내림차순으로 순열을 구하기 때문에 "내림차순으로 정렬된 값을 가진 컨테이너"를 사용해야 모든 순열 조합을 구할 수 있습니다.

{1, 2, 3} 으로 정렬되어 있는 배열을 사용하면, 더 이상 내림차순으로 정렬할 수 없어 이전 순열은 구할 수 없습니다.

 vector<int> v{2, 1, 3};
    sort(v.begin(), v.end(), greater<int>());  // {3, 2, 1}
    do{
        for(auto& it : v){
            cout << it << " ";
        }
        cout << endl;

    }while(prev_permutation(v.begin(), v.end()));

 

2차원 벡터의 순열 구하기

첫번째 벡터를 기준으로 순열을 구하는 코드입니다.

bool cmp(vector<int> &a, vector<int>& b){
    if(a[0] == b[0]){
        return a[1] > b[1];
    }
    else{
        return a[0] > b[0];
    }
}

int main(){

    vector<vector<int>> vec = { 
        {80, 20}, {50, 40}, {30, 10}
    };

    int k = 80;

     sort(vec.begin(), vec.end(), cmp);

     do{
        cout << vec[0][0] << "," << vec[0][1] << endl;
        cout << vec[1][0] << "," << vec[1][1] << endl;
        cout << vec[2][0] << "," << vec[2][1] << endl;
        cout << endl;
  
     }while(prev_permutation(vec.begin(), vec.end()));

    return 0;
}