std:: next_permutation

범위 [ first , last ) 를 다음 순열 로 재배열합니다. "다음 순열"이 존재할 경우 true 를 반환하고, 그렇지 않을 경우 범위를 사전식 첫 번째 순열로 변환한 후( std::sort 를 사용한 것처럼) false 를 반환합니다.

만약 * first 의 타입이 Swappable 가 아닌 경우 (C++11 이전) BidirIt 이 ValueSwappable 가 아닌 경우 (C++11 이후) , 동작은 정의되지 않습니다.

매개변수

반환값

true 새로운 순열이 이전 순열보다 사전식 순서에서 더 큰 경우. false 마지막 순열에 도달했고 범위가 첫 번째 순열로 재설정된 경우.

복잡도

주어진 \(\scriptsize N\) N 이 std:: distance ( first, last ) 인 경우:

예외

반복자 연산 또는 요소 교체에서 발생하는 모든 예외.

가능한 구현

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    auto r_first = std::make_reverse_iterator(last);
    auto r_last = std::make_reverse_iterator(first);
    auto left = std::is_sorted_until(r_first, r_last);
    if (left != r_last)
    {
        auto right = std::upper_bound(r_first, left, *left);
        std::iter_swap(left, right);
    }
    std::reverse(left.base(), last);
    return left != r_last;
}

참고 사항

전체 순열 시퀀스에 걸쳐 평균적으로, 일반적인 구현은 호출당 약 3회의 비교와 1.5회의 스왑을 사용합니다.

구현체들(예: MSVC STL )은 반복자 타입이 LegacyContiguousIterator 요구사항을 만족하고 해당 값 타입의 스왑 연산이 비트리비얼 특수 멤버 함수를 호출하지 않으며 ADL 에서 발견된 swap 을 호출하지 않을 때 벡터화를 활성화할 수 있습니다.

예제

#include <algorithm>
#include <iostream>
#include <string>
int main()
{
    std::string s = "aba";
    do
    {
        std::cout << s << '\n';
    }
    while (std::next_permutation(s.begin(), s.end()));
    std::cout << s << '\n';
}

aba
baa
aab

참고 항목