[C++] STL next_permutation을 공부하자

오늘은 C++의 STL 중 next_permutation을 공부해 보자.

STL에는 컨테이너와 알고리즘 등이 있다고 했는데, next_permutation은 알고리즘에 해당한다.

그래서 사용하기 위해서는 algorithm 헤더를 추가해야 한다.

그럼 오늘은 permutation의 개념을 알아보고 next_permutation 활용 코드를 보자.

---

---

permutation 이란?

permutation이란 순열을 의미한다.

예를 들어 1, 2, 3에서 3개를 뽑는 경우의 수는 (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) 등이 있다.

앞에서 뽑았던 숫자를 다시 뽑더라도 순서를 고려해서 다른 경우의 수로 보는 것이 순열이다.

 

next_permutation 이란?

next_permutation은 이름 그대로 다음 순열을 의미한다.

순열 (1, 2, 3)의 다음 순열은 (1, 3, 2)인데, 이것이 바로 next permutation이다.

 

코드 구현

그럼 next_permutation 코드에 대해서 알아보자.

먼저 함수 원형이다.

bool next_permutation(BidirectionIterator first, BidirectionIterator last);

 

1) 반환형

next_permutation의 반환형은 bool 형이다.

다음 순열이 존재한다면 true를 return하고, 존재하지 않는다면 false를 return한다.

 

2) 인자

BidirectionIterator first와 BidirectionIterator last는 시작과 끝을 의미하는데, 배열과 벡터가 다른 형태로 구현하지만 의미는 동일하지 예제 코드를 통해 알아보자.

 

먼저 배열 코드이다.

// 배열 arr와 길이 N이 선언되어 있음을 가정한다

next_permutation(arr, arr+N);

 

배열의 경우 first로 배열 이름을 그대로 넣어주고, last로 배열이름+길이를 넣어준다.

이렇게 작성하면 배열의 첫 주소와 마지막 주소를 넣는 것이 된다.

 

다음은 벡터 코드이다.

// 벡터 v가 생성되어 있다고 가정

next_permutation(v.begin(), v.end());

 

vector의 경우 first를 v.begin(), last를 v.end()로 작성한다.

이렇게 작성해서 넘겨주면 다음 순열을 확인하여 true나 false의 반환값을 return하고, 배열이나 벡터에 다음 순열이 저장된다.

 

3) 전체 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int N = 3;
    int arr[10] = {1, 2, 3};
    
    if(next_permutation(arr, arr+N))
    {
        for(int i=0; i<N; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
    else
        cout << "다음 순열 없음" << endl;
    
    return 0;
}

 

next_permutation을 활용하기 위해 algorithm 헤더 파일을 추가한다.

if 문 내에 조건으로 next_permutation을 넣고 다음 순열이 존재 할 경우 true를 return하고, arr에 다음 순열을 저장한다.

그리고 그 값을 출력하도록 코드를 작성했다.

만약 다음 순열이 없는 순열이라면 else문을 통해 위와 같은 코드를 출력하도록 한다.

---

오늘은 permutation의 개념을 알아보고, next_permutation을 활용해 코드를 작성해 보았다.

직접 next_permutation을 활용한 코드를 작성해 보면서 연습을 해보면 좋겠다.