[C/C++] Next_permutation 사용법

• 이 글은 C++의 Next_permutation API 사용법입니다.

Next_permutation

• C++에서 순열과 조합을 구현하기 위해서 대표적인 방법으로 백트래킹(backtraking) 기법을 사용합니다.

• 백트래킹 기법을 이용하는 것 이외에도 C++에서는 순열, 조합을 구현하기 위한 API인 Next_permutation 함수가 존재합니다.

• 보다 빠르게 작성할 수 있기 때문에 순열, 조합으로도 충분히 통과할 만한 문제인 경우 다음 API를 사용하면 좋습니다.

• next_premutation 함수를 사용하기 위해서는 #include< algorithm >을 선언하여야 합니다.

Example

int main(){
    int arr[3] = {3,1,2};
    sort(arr, arr+3);

    /**
     1 2 3
     1 3 2
     2 1 3
     2 3 1
     3 1 2
     3 2 1
     */
    do{
        for(int i=0;i<3;i++){
            cout<<arr[i]<<' ';
        }
        cout<<endl;
    }while(next_permutation(arr, arr+3));
    cout<<endl;
 }

다음과 같이 next_premutation을 사용하기 전에 arr를 오름차순으로 정렬을 해두어야 합니다.
next_permutation에서 3번째 매개변수는 compare 함수를 넣어서 정렬방식을 바꿔도 되지만, Default 값으로는 오름차순으로 배열이 바뀌게 됩니다.

int main(){
    int arr2[3] = {1,2,1};
    sort(arr2, arr2+3);

    /**
     1 1 2
     1 2 1
     2 1 1
     */
    do{
        for(int i=0;i<3;i++){
            cout<<arr2[i]<<' ';
        }
        cout<<endl;
    }while(next_permutation(arr2, arr2+3));
    cout<<endl;
 }

중복된 원소가 있더라도 문제 없이 순열의 결과가 나타난 것을 확인할 수 있습니다.

  int main(){
    int arr3[4] = {1,2,3,4};
    int check[4] = {0,1,0,1};
    sort(check, check+4);

    /**
     1 2
     1 3
     1 4
     2 3
     2 4
     3 4
     */
    do{
        for(int i=0;i<4;i++){
            if(!check[i]){
                cout<<arr3[i]<<' ';
            }
        }
        cout<<endl;
    }while(next_permutation(check, check+4));
 }

순열이 아닌 조합을 사용할 때는 원소가 들어있는 시퀀스를 next_permutation을 하는게 아닌 0과 1이 들어있는 check 배열을 가지고 사용하게 됩니다.
예를 들어 4C2 즉, 4개가 있는 원소 중 2개를 뽑아서 보여주는 함수일 경우 0을 2개 , 1을 2개가 들어있는 check 배열을 만듭니다. 마찬가지로 오름차순으로 정렬시킨 후 0이 있는 인덱스와 동일한 arr 원소를 출력하면 됩니다.