STL - next_permutation

현재 탐색하고 있는 순열의 다음 순열을 구하고 true를 반환한다. 만약, 다음 순열이 존재하지 않는다면 false를 반환한다.

즉, 마지막 모든 순열의 경우의 수를 탐색한 뒤, false를 반환한다.

 

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;
}

 

Time Complexity

비교를 진행하면서, N/2만큼 swap을 진행한다. 이때, N = std::distance(first, last)이다.

즉, 시간 복잡도는 O(N)이다.