std::next_permutation

template< class BidirIt >
bool next_permutation( BidirIt first, BidirIt last );

template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );

범위 [first, last) 를 다음 순열로 순열합니다. 그러한 "다음 순열"이 존재하면 true 를 반환하며, 그렇지 않으면 범위를 사전식 첫 번째 순열(오름차순)로 변환하고 false 를 반환합니다.

만약 의 타입이 *first Swappable(C++11까지)BidirIt ValueSwappable(C++11부터)이 아니라면, 동작은 정의되지 않습니다.

매개변수

의 요구 사항을 충족해야 합니다.

true반환값false새 순열이 이전 순열보다 사전식으로 더 큰 경우

. 마지막 순열에 도달하여 범위가 첫 번째 순열로 재설정된 경우

. 복잡도\(\scriptsize N\)Nstd::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 <cassert>
#include <iostream>
#include <string>

int main()
{
    std::string s = "ABBA";
    std::sort(s.begin(), s.end());
    
    do
        std::cout << s << '\n';
    while (std::next_permutation(s.begin(), s.end()));

    assert(std::is_sorted(s.begin(), s.end()));
}

AABB
ABAB
ABBA
BAAB
BABA
BBAA

같이 보기