std::ranges::prev_permutation, std::ranges::prev_permutation_result

헤더에 정의됨 `<algorithm>`
호출 시그니처
template< std::bidirectional_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<I, Comp, Proj> constexpr prev_permutation_result<I> prev_permutation( I first, S last, Comp comp = {}, Proj proj = {} );	(1)	(C++20부터)
template< ranges::bidirectional_range R, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr prev_permutation_result<ranges::borrowed_iterator_t<R>> prev_permutation( R&& r, Comp comp = {}, Proj proj = {} );	(2)	(C++20부터)
도우미 타입
template< class I > using prev_permutation_result = ranges::in_found_result<I>;	(3)	(C++20부터)

1) 범위를 이전 [first, last) permutation으로 변환합니다. 여기서 모든 순열의 집합은 이진 비교 함수 객체 lexicographically와 투영 함수 객체에 대해 사전식으로 정렬됩니다.compproj 반환:

"이전" 순열이 존재하면 true입니다.

{last, true} 그렇지 않으면 false를 반환하고,
{last, false} 범위를 사전식으로 마지막 순열(내림차순)로 변환합니다.

2) (1)과 동일하지만, (1)을 사용하고,r r을 소스 범위로 사용하여,ranges::begin(r) ranges::begin(r)first을 first로,ranges::end(r) ranges::end(r)last을 last로 사용하는 것처럼 동작합니다.

이 페이지에 설명된 함수형 엔티티는 알고리즘 함수 객체입니다 (비공식적으로 niebloids라고 함). 즉:

명시적 템플릿 인자 목록을 지정하여 호출할 수 없습니다.
그들 중 어느 것도 인자 의존적 조회에 보이지 않습니다.
그들 중 하나가 정규 비한정 조회에 의해 함수 호출 연산자의 왼쪽에 있는 이름으로 발견되면,인자 의존적 조회가 억제됩니다.

매개변수

first, last	-	"순열"할 요소들의 범위 를 정의하는 반복자-감시자 쌍
r	-	"순열"할 요소들의 `range` 범위
comp	-	첫 번째 인수가 두 번째 인수보다 작으면 true 를 반환하는 비교 FunctionObject
proj	-	요소에 적용할 투영(projection)

반환값

1) ranges :: prev_permutation_result < I > { last, true } 새로운 순열이 이전 순열보다 사전순으로 작은 경우. ranges :: prev_permutation_result < I > { last, false } 첫 번째 순열에 도달하고 범위가 마지막 순열로 재설정된 경우.

2) (1) 과 동일하지만 반환 타입이 ranges :: prev_permutation_result < ranges:: borrowed_iterator_t < R >> 입니다.

예외

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

복잡도

최대 $\scriptsize N/2$ $N / 2$ 회의 교환, 여기서 $\scriptsize N$ $N$ 은 ranges:: distance ( first, last ) (경우 (1) ) 또는 ranges:: distance ( r ) (경우 (2) )입니다. 전체 순열 시퀀스에 걸쳐 평균적으로, 일반적인 구현은 호출당 약 3회의 비교와 1.5회의 교환을 사용합니다.

참고 사항

구현체들(예: MSVC STL )은 반복자 타입이 contiguous_iterator 를 모델링하고, 그 값 타입의 스왑 연산이 비트리비얼 특수 멤버 함수나 ADL 에 의해 발견된 swap 을 호출하지 않을 때 벡터화를 활성화할 수 있습니다.

가능한 구현

struct prev_permutation_fn
{
    template<std::bidirectional_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr ranges::prev_permutation_result<I>
        operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        // 시퀀스에 최소 두 개의 요소가 있는지 확인
        if (first == last)
            return {std::move(first), false};
        auto i{first};
        ++i;
        if (i == last)
            return {std::move(i), false};
        auto i_last{ranges::next(first, last)};
        i = i_last;
        --i;
        // 주요 "순열 생성" 루프
        for (;;)
        {
            auto i1{i};
            --i;
            if (std::invoke(comp, std::invoke(proj, *i1), std::invoke(proj, *i)))
            {
                auto j{i_last};
                while (!std::invoke(comp, std::invoke(proj, *--j), std::invoke(proj, *i)))
                    ;
                ranges::iter_swap(i, j);
                ranges::reverse(i1, last);
                return {std::move(i_last), true};
            }
            // 순열 "공간"이 소진됨
            if (i == first)
            {
                ranges::reverse(first, last);
                return {std::move(i_last), false};
            }
        }
    }
    template<ranges::bidirectional_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::prev_permutation_result<ranges::borrowed_iterator_t<R>>
        operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r),
                       std::move(comp), std::move(proj));
    }
};
inline constexpr prev_permutation_fn prev_permutation {};

예제

이 코드 실행

#include <algorithm>
#include <array>
#include <compare>
#include <functional>
#include <iostream>
#include <string>
struct S
{
    char c{};
    int i{};
    auto operator<=>(const S&) const = default;
    friend std::ostream& operator<<(std::ostream& os, const S& s)
    {
        return os << "{'" << s.c << "', " << s.i << "}";
    }
};
auto print = [](auto const& v, char term = ' ')
{
    std::cout << "{ ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '}' << term;
};
int main()
{
    std::cout << "Generate all permutations (iterators case):\n";
    std::string s{"cba"};
    do print(s);
    while (std::ranges::prev_permutation(s.begin(), s.end()).found);
    std::cout << "\nGenerate all permutations (range case):\n";
    std::array a{'c', 'b', 'a'};
    do print(a);
    while (std::ranges::prev_permutation(a).found);
    std::cout << "\nGenerate all permutations using comparator:\n";
    using namespace std::literals;
    std::array z{"▁"s, "▄"s, "█"s};
    do print(z);
    while (std::ranges::prev_permutation(z, std::greater()).found);
    std::cout << "\nGenerate all permutations using projection:\n";
    std::array<S, 3> r{S{'C',1}, S{'B',2}, S{'A',3}};
    do print(r, '\n');
    while (std::ranges::prev_permutation(r, {}, &S::c).found);
}

출력:

Generate all permutations (iterators case):
{ c b a } { c a b } { b c a } { b a c } { a c b } { a b c }
Generate all permutations (range case):
{ c b a } { c a b } { b c a } { b a c } { a c b } { a b c }
Generate all permutations using comparator:
{ ▁ ▄ █ } { ▁ █ ▄ } { ▄ ▁ █ } { ▄ █ ▁ } { █ ▁ ▄ } { █ ▄ ▁ }
Generate all permutations using projection:
{ {'C', 1} {'B', 2} {'A', 3} }
{ {'C', 1} {'A', 3} {'B', 2} }
{ {'B', 2} {'C', 1} {'A', 3} }
{ {'B', 2} {'A', 3} {'C', 1} }
{ {'A', 3} {'C', 1} {'B', 2} }
{ {'A', 3} {'B', 2} {'C', 1} }

같이 보기

ranges::next_permutation (C++20)	요소 범위의 다음으로 큰 사전식 순열을 생성합니다 (알고리즘 함수 객체)
ranges::is_permutation (C++20)	시퀀스가 다른 시퀀스의 순열인지 판별합니다 (알고리즘 함수 객체)
next_permutation	요소 범위의 다음으로 큰 사전식 순열을 생성합니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::next_permutation (C++20)	요소 범위의 다음으로 큰 사전식 순열을 생성합니다 (함수 템플릿 & 알고리즘 함수 객체)
prev_permutation	요소 범위의 다음으로 작은 사전식 순열을 생성합니다 (함수 템플릿)
is_permutation (C++11)	시퀀스가 다른 시퀀스의 순열인지 판별합니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::is_permutation (C++20)	시퀀스가 다른 시퀀스의 순열인지 판별합니다 (함수 템플릿 & 알고리즘 함수 객체)

컴파일러 지원
프리스탠딩 및 호스티드
언어
표준 라이브러리
표준 라이브러리 헤더
명명된 요구 사항
기능 테스트 매크로 (C++20)
언어 지원 라이브러리
개념 라이브러리 (C++20)
진단 라이브러리
메모리 관리 라이브러리
메타프로그래밍 라이브러리 (C++11)
일반 유틸리티 라이브러리
컨테이너 라이브러리
반복자 라이브러리
범위 라이브러리 (C++20)
알고리즘 라이브러리
문자열 라이브러리
텍스트 처리 라이브러리
수치 라이브러리
날짜 및 시간 라이브러리
입출력 라이브러리
파일 시스템 라이브러리 (C++17)
동시성 지원 라이브러리 (C++11)
실행 제어 라이브러리 (C++26)
기술 명세서
기호 색인
외부 라이브러리

ko.cppreference.net

Namespaces

Variants

std::ranges::prev_permutation, std::ranges::prev_permutation_result

목차

매개변수

반환값

예외

복잡도

참고 사항

가능한 구현

예제

같이 보기