Namespaces
Variants

    std::is_permutation

    cppreference.net에서
     
    C++
     
    알고리즘 라이브러리
    제약된 알고리즘과 범위 기반 알고리즘 (C++20)
    제약된 알고리즘 (예: ranges::copy, ranges::sort, ...)
    정렬 및 관련 연산
    분할 연산
    (C++11)    
    (C++11)

    정렬 연산
    이진 탐색 연산
    (분할된 범위에서)
    집합 연산 (정렬된 범위에서)
    병합 연산 (정렬된 범위에서)
    힙 연산
    최소/최대 연산
    (C++11)
    (C++17)
    사전식 비교 연산
    (C++20)
    순열 연산


     
    헤더 <algorithm> 
    template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2 );
    		에 정의됨 (1) (C++11부터)
    (C++20부터 constexpr) 
    template< class ForwardIt1, class ForwardIt2,
          class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, BinaryPredicate p );
    		(2) (C++11부터)
    (C++20부터 constexpr) 
    template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, ForwardIt2 last2 );
    		(3) (C++14부터)
    (C++20부터 constexpr) 
    template< class ForwardIt1, class ForwardIt2,
          class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, ForwardIt2 last2,
                     BinaryPredicate p );
    		(4) (C++14부터)
    (C++20부터 constexpr)

    [first1, last1)이 순열인지 first2부터 시작하는 범위의 검사:

    • 오버로드 (1,2)의 경우, 두 번째 범위는 std::distance(first1, last1) 개의 요소를 갖습니다.
    • 오버로드 (3,4)의 경우, 두 번째 범위는 [first2, last2)입니다.
    1,3) 요소들은 operator==를 사용하여 비교됩니다.
    2,4) 요소들은 주어진 이진 술어 p를 사용하여 비교됩니다.

    만약 ForwardIt1과 ForwardIt2이 서로 다른 값 타입을 가지면, 프로그램은 잘못된 형태입니다(ill-formed).

    비교 함수가 동치 관계가 아니라면, 동작은 정의되지 않습니다.

    매개변수

    first1, last1 - 비교할 첫 번째 요소 범위를 정의하는 반복자 쌍
    first2, last2 - 비교할 두 번째 요소 범위를 정의하는 반복자 쌍
    p - 요소가 동등한 것으로 처리되어야 하면 ​true을 반환하는 이진 술어.

    술어 함수의 시그니처는 다음과 동등해야 합니다:

    bool pred(const Type1 &a, const Type2 &b);

    시그니처에 const &가 있을 필요는 없지만, 함수는 전달된 객체를 수정해서는 안 되며, Type1과 Type2 타입(상수 가능)의 모든 값을 값 범주에 관계없이 받아들일 수 있어야 합니다 (따라서 Type1 &는 허용되지 않으며, Type1도 이동이 복사와 동등하지 않은 한 허용되지 않습니다Type1(C++11부터)).
    타입 Type1과 Type2은 각각 InputIt1과 InputIt2 타입의 객체를 역참조한 후 암시적으로 Type1과 Type2로 변환될 수 있어야 합니다. ​

    타입 요구사항
    -
    ForwardIt1, ForwardIt2은 LegacyForwardIterator의 요구사항을 충족해야 합니다.

    반환값

    true범위 [first1, last1)이 범위 [first2, last2)의 순열이면 false, 그렇지 않으면

    입니다.

    복잡도\(\scriptsize N\)Nstd::distance(first1, last1)이

    일 때: 1)\(\scriptsize N\)Noperator== 번의 \(\scriptsize O(N^2)\)O(N
    2    ) 번의 비교가 이루어집니다.
    2) 두 범위가 같으면 정확히 N 번의 술어 p 적용이 이루어지고, 그렇지 않으면 최악의 경우 O(N2
    ) 번의 적용이 이루어집니다.    3,4)
    과 ForwardIt1이 모두 ForwardIt2LegacyRandomAccessIterator이고 과 last1 - first1 != last2 - first2이 true이면, 비교가 이루어지지 않습니다.
    그렇지 않으면:
    3) 두 범위가 같으면 정확히 N 번의 operator==를 사용한 비교가 이루어지고, 그렇지 않으면 최악의 경우 O(N2
    ) 번의 비교가 이루어집니다.    4)
    두 범위가 같으면 정확히 \(\scriptsize N\) 번의 술어 적용이 이루어지고, 그렇지 않으면 최악의 경우 p\(\scriptsize O(N^2)\)2) 번의 적용이 이루어집니다.
    가능한 구현    참고

    template<class ForwardIt1, class ForwardIt2>
bool is_permutation(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 d_first)
{
    // skip common prefix
    std::tie(first, d_first) = std::mismatch(first, last, d_first);
    
    // iterate over the rest, counting how many times each element
    // from [first, last) appears in [d_first, d_last)
    if (first != last)
    {
        ForwardIt2 d_last = std::next(d_first, std::distance(first, last));
        for (ForwardIt1 i = first; i != last; ++i)
        {
            if (i != std::find(first, i, *i))
                continue; // this *i has been checked
            
            auto m = std::count(d_first, d_last, *i);
            if (m == 0 || std::count(i, last, *i) != m)
                return false;
        }
    }
    return true;
}

    는 std::is_permutation테스트에 사용될 수 있습니다. 즉, 재배열 알고리즘(예: 정렬, 섞기, 분할)의 정확성을 확인하는 데 사용됩니다. 이 원래 범위이고 x이 y순열된 범위라면, 는 std::is_permutation(x, y) == true이 y"동일한" 요소들로 구성되어 있지만 다른 위치에 있을 수 있음을 의미합니다. 예제

    이 코드 실행

    출력: 
    #include <algorithm>
#include <iostream>

template<typename Os, typename V>
Os& operator<<(Os& os, const V& v)
{
    os << "{ ";
    for (const auto& e : v)
        os << e << ' ';
    return os << '}';
}

int main()
{
    static constexpr auto v1 = {1, 2, 3, 4, 5};
    static constexpr auto v2 = {3, 5, 4, 1, 2};
    static constexpr auto v3 = {3, 5, 4, 1, 1};
    
    std::cout << v2 << " is a permutation of " << v1 << ": " << std::boolalpha
              << std::is_permutation(v1.begin(), v1.end(), v2.begin()) << '\n'
              << v3 << " is a permutation of " << v1 << ": "
              << std::is_permutation(v1.begin(), v1.end(), v3.begin()) << '\n';
}

    같이 보기

    { 3 5 4 1 2 } is a permutation of { 1 2 3 4 5 }: true
{ 3 5 4 1 1 } is a permutation of { 1 2 3 4 5 }: false

    next_permutation

    		 (함수 템플릿
    알고리즘 함수 객체)&ranges::next_permutation
    prev_permutation
    		(함수 템플릿
    알고리즘 함수 객체)&ranges::prev_permutation
    equivalence_relation
    		관계가 동치 관계를 부과함을 지정합니다. (개념)
    ranges::is_permutation
    하나의 시퀀스가 다른 시퀀스의 순열인지 결정합니다.
    		 (알고리즘 함수 객체)