등장범위: 완전 탐색-순열, 조합
algorithm 헤더 파일 안에 정의되어 있음
동작 내용: [첫 번째, 마지막] 범위를 다음 순열로 바꾸어 나열한다. 여기서 모든 순열의 집합은 연산자 < 또는 comp에 대해 사전 순서로 정렬된다.
이러한 다음 순열이 있으면 true 반환하고, 그렇지 않으면 범위를 사전 형식적으로 첫 번째 순열(std::sort(first,last,comp)로 변환하고 false를 반환한다.
parameter:
first,last - 순서대로 정렬할 원소의 범위
comp- 첫 번째 인수가 두 번째 인수보다 작을 경우 true를 반환하는 비교 함수 객체(즉 compare의 요구 사항을 충족하는 객체)
비교 기능의 코드는 다음과 같아야 한다.
bool cmp(const Type1 &a, const Type2 &b);
: 꼭 const&가 필요한 것은 아니지만 함수는 전달한 객체를 변경할 수 없고 모든 형식의 값을 허용할 수 있어야 한다.(가능하면 const) 값 범주에 관계없이 Type1과 Type2는 허용되지 않으며, Type1의 이동이 사본과 동일하지 않는 한 Type1도 허용되지 않는다.(c++11 이후)
Type1과 Type2는 BidirIt 유형의 객체를 참조 취소한 다음 암시적으로 둘 다로 변환할 수 있도록 해야 한다.
Return value
: 사전적으로 새 순열이 이전 순열보다 크면 true를 반환하고, 마지막 순열에 도달하고 범위가 첫 번째 순열로 재설정되면 false를 반환한다.
Exceptions
:반복자 실행 혹은 요소 swap에서 발생한 예외
Complexity
: 많아봤자 N/2 swap(여기서 N=std::distance(첫 번째, 마지막)). 순열의 전체 시퀀스에 걸쳐 평균화된 일반적인 구현은 약 3번의 비교와 1.5번 swap을 사용한다.
코드 예시
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int main()
{
string s="aba";
sort(s.begin(),s.end());
do{
cout << s << endl;
}while(next_permutation(s.begin(),s.end()));
}output:
aab
aba
baa
