[ C++ ] 순열을 구할 수 있는 함수 next_permutation

C++에서 algorithm 헤더파일에서 순열을 구할 수 있는 함수가 있다.

 

함수에 벡터의 iterator 혹은 배열의 주소를 넣으면 다음 순열 혹은 이전 순열의 결과를 벡터나 배열에 적용할 수 있다. 예를 들어 1-2-3-4의 다음 순열은 1-2-4-3, 1-2-4-3의 이전 순열은 1-2-3-4 이다.

 

- next_permutation : 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환한다.

- prev_permutation : 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 크다면) false를 반환한다.

// 첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

// 세번째 인자로 비교함수를 입력할수도 있다.
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

 

* 주의할점 *

순열 함수를 사용하기 전에 배열/벡터가 오름차순으로 정렬되어 있어야한다.

그래야 모든 경우의 수를 탐색할 수 있다.

 

 

 

<구현 코드>

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int arr[3] = {4,5,1};
    int size = sizeof(arr)/sizeof(arr[0]);

    // 순열 함수 사용 전에 오름차순으로 정렬하기
    sort(arr, arr+size);
    
    // next_permutation을 통해서 다음 순열 구하기
    do{
        for(int i=0; i<size; i++){
            cout << arr[i] << " ";
        }
        cout << "\n";
    } while(next_permutation(arr, arr+size));

    return 0;
}

 

실행 결과