std::ranges::next_permutation, std::ranges::next_permutation_result

(C++23)`<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 next_permutation_result<I> next_permutation( I first, S last, Comp comp = {}, Proj proj = {} );	에 정의됨	호출 시그니처
template< ranges::bidirectional_range R, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr next_permutation_result<ranges::borrowed_iterator_t<R>> next_permutation( R&& r, Comp comp = {}, Proj proj = {} );	(1)	(C++20부터)
(2)
template< class I > using next_permutation_result = ranges::in_found_result<I>;	(C++20부터)	헬퍼 타입

(3) (C++20부터)[first, last)1) 모든 순열의 집합이 이진 비교 함수 객체 및 투영 함수 객체 에 대해 사전순으로comp 정렬될 때, 범위 proj을 다음 {last, true}순열로 변환합니다. 그러한 "다음 순열"이 존재하면 {last, false}을 반환합니다. 그렇지 않으면 범위를 사전순으로 첫 번째 순열(오름차순)로 변환하고

을 반환합니다.2) (1)과 동일하지만, r을 소스 범위로 사용하며, 이는 ranges::begin(r)을 first로, ranges::end(r)을 last로 사용하는 것과 같습니다.

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

이들 중 하나를 호출할 때 명시적 템플릿 인자 목록을 지정할 수 없습니다.
이들 중 어느 것도 인자 종속 검색에 표시되지 않습니다.
이들 중 하나가 일반적인 비한정 검색에 의해 함수 호출 연산자 왼쪽의 이름으로 발견되면, 인자 종속 검색이 억제됩니다.

매개변수

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

반환값

1) ranges :: next_permutation_result < I > { last, true } 새로운 순열이 이전 순열보다 사전식 순서로 더 큰 경우. ranges :: next_permutation_result < I > { last, false } 마지막 순열에 도달했고 범위가 첫 번째 순열로 재설정된 경우.

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

예외

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

복잡도

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

참고 사항

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

가능한 구현

struct next_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::next_permutation_result<I>
        operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        // 시퀀스에 최소 두 개의 요소가 있는지 확인
        if (first == last)
            return {std::move(first), false};
        I i_last{ranges::next(first, last)};
        I i{i_last};
        if (first == --i)
            return {std::move(i_last), false};
        // 주요 "순열 생성" 루프
        for (;;)
        {
            I i1{i};
            if (std::invoke(comp, std::invoke(proj, *--i), std::invoke(proj, *i1)))
            {
                I j{i_last};
                while (!std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *--j)))
                {}
                std::iter_swap(i, j);
                std::reverse(i1, i_last);
                return {std::move(i_last), true};
            }
            // 순열 "공간"이 소진됨
            if (i == first)
            {
                std::reverse(first, i_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::next_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 next_permutation_fn next_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{"abc"};
    do
    {
        print(s);
    }
    while (std::ranges::next_permutation(s.begin(), s.end()).found);
    std::cout << "\n" "Generate all permutations (range case):\n";
    std::array a{'a', 'b', 'c'};
    do
    {
        print(a);
    }
    while (std::ranges::next_permutation(a).found);
    std::cout << "\n" "Generate all permutations using comparator:\n";
    using namespace std::literals;
    std::array z{"█"s, "▄"s, "▁"s};
    do
    {
        print(z);
    }
    while (std::ranges::next_permutation(z, std::greater()).found);
    std::cout << "\n" "Generate all permutations using projection:\n";
    std::array<S, 3> r{S{'A',3}, S{'B',2}, S{'C',1}};
    do
    {
        print(r, '\n');
    }
    while (std::ranges::next_permutation(r, {}, &S::c).found);
}

출력:

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

참고 항목

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

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

ko.cppreference.net

Namespaces

Variants

std::ranges::next_permutation, std::ranges::next_permutation_result

목차

매개변수

반환값

예외

복잡도

참고 사항

가능한 구현

예제

참고 항목