algorithm_next_permutation
algorithm_next_permutation (다음 순열)
std::next_permutation는 범위를 사전식 순서상 다음 순열로 바꿔요. 모든 순열을 순회하는 반복 패턴에 써요.
출처: cppreference
본문
std::next_permutation는 범위 [first, last)를 다음 순열로 재배열해요. 다음 순열이 존재하면 true를, 그렇지 않으면 범위를 사전식 첫 번째 순열(오름차순)로 바꾸고 false를 돌려줘요. <algorithm> 헤더에 정의되어 있어요.
template< class BidirIt >
bool next_permutation( BidirIt first, BidirIt last );
template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );
- 1번 오버로드 — 모든 순열이
operator<(즉std::less{})를 기준으로 사전식으로 정렬돼 있어요. - 2번 오버로드 — 모든 순열이 비교 함수
comp를 기준으로 정렬돼 있어요.
반환값 (Return value)
다음 순열로 바뀌었으면 true, 마지막 순열이라 오름차순으로 되돌아가면 false예요.
복잡도 (Complexity)
최악의 경우 N을 std::distance(first, last)라고 할 때 반복자와 요소의 스왑을 합쳐 𝓞(N)이에요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{1, 2, 3};
do {
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
} while (std::next_permutation(v.begin(), v.end()));
}
출력:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1