Related to: Algorithms
개요
C++ STL <algorithm> 헤더에서 제공하는 next_permutation 함수를 사용하는 방법입니다.
핵심 개념
특징
- 기본적으로 배열의 iterator를 param으로 받는다. 입력 배열의 내부 원소 위치만 바꾸기(swap) 때문에 메모리가 새롭게 생성되지 않는다.
- 따라서 모든 경우의 수를 배열로 얻어야 한다면 loop 내에서 계속 호출하며 별도의 컨테이너에 복사해야 한다.
- 배열을 오름차순으로 정렬하고 사용해야 한다. 변경 전 배열을 A, 변경 후 배열을 B라고 할 때 사전식(lexicographically) 순서로 비교하여 B가 A보다 크다면 true를 반환하고 그렇지 않다면 false를 반환한다.
- 리턴 값(bool)이 false라면 새로운 순열이 더 이상 없다고 간주하고 loop를 종료한다.
예시 / 코드
Header
#include<algorithm>함수 시그니처
template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last );
or
template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );사용 예제
\#include <algorithm>
\#include <string>
\#include <iostream>
int main()
{
std::string s = "aba";
std::sort(s.begin(), s.end());
do {
std::cout << s << '\n';
} while(std::next_permutation(s.begin(), s.end()));
}