std::is_permutation

Определён в заголовке `<algorithm>`
template< class ForwardIt1, class ForwardIt2 > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );	(1)	(начиная с C++11) (constexpr начиная с C++20)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, BinaryPredicate p );	(2)	(начиная с C++11) (constexpr начиная с C++20)
template< class ForwardIt1, class ForwardIt2 > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(3)	(начиная с C++14) (constexpr начиная с C++20)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p );	(4)	(начиная с C++14) (constexpr начиная с C++20)

Проверяет, является ли [first1, last1) перестановкой диапазона, начинающегося с first2:

Для перегрузок (1,2) второй диапазон содержит std::distance(first1, last1) элементов.
Для перегрузок (3,4) второй диапазон задаётся [first2, last2).

1,3) Элементы сравниваются с помощью operator==.

2,4) Элементы сравниваются с помощью заданного бинарного предиката p.

Если ForwardIt1 и ForwardIt2 имеют разные типы значений, программа некорректна.

Если функция сравнения не является отношением эквивалентности, поведение не определено.

Параметры

first1, last1	-	пара итераторов, определяющая первый диапазон элементов для сравнения
first2, last2	-	пара итераторов, определяющая второй диапазон элементов для сравнения
p	-	бинарный предикат, который возвращает `true`, если элементы следует считать равными. Сигнатура функции-предиката должна быть эквивалентна следующей: boolpred(constType1&a,constType2&b); Хотя сигнатура не обязана содержать `const &`, функция не должна изменять переданные ей объекты и должна принимать любые значения типа (возможно, 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\)N — std::distance(first1, last1):

1) Ровно \(\scriptsize N\)N сравнений с помощью operator==, если диапазоны равны, иначе в худшем случае \(\scriptsize O(N^2)\)O(N²) сравнений.

2) Ровно \(\scriptsize N\)N вызовов предиката p, если диапазоны равны, иначе в худшем случае \(\scriptsize O(N^2)\)O(N²) вызовов.

3,4) Если ForwardIt1 и ForwardIt2 являются LegacyRandomAccessIterator, а last1 - first1 != last2 - first2 — true, сравнения не выполняются.

В противном случае:

3) Ровно \(\scriptsize N\)N сравнений с помощью operator==, если диапазоны равны, иначе в худшем случае \(\scriptsize O(N^2)\)O(N²) сравнений.

4) Ровно \(\scriptsize N\)N вызовов предиката p, если диапазоны равны, иначе в худшем случае \(\scriptsize O(N^2)\)O(N²) вызовов.

Возможная реализация

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 (C++20)
prev_permutation	генерирует следующую лексикографически меньшую перестановку диапазона элементов (шаблон функции и функциональный объект алгоритма)
ranges::prev_permutation (C++20)
equivalence_relation (C++20)	указывает, что `relation` задаёт отношение эквивалентности (концепт)
ranges::is_permutation (C++20)	определяет, является ли одна последовательность перестановкой другой последовательности (функциональный объект алгоритма)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/is_permutation