std::is_permutation

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

Возвращает true , если существует перестановка элементов в диапазоне [first1, last1), которая делает этот диапазон равным диапазону [first2, last2), где last2 обозначает first2 + (last1 - first1) , если оно не было задано.

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

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

Параметры

first1, last1	-	диапазон элементов для сравнения
first2, last2	-	второй диапазон для сравнения
p	-	бинарный предикат, который возвращает `true` , если элементы должны рассматриваться как равные. Подпись функции-предиката должна быть эквивалентна следующей: `bool pred(const Type &a, const Type &b);` `Type` должна быть типом значения как для `ForwardIt1`, так и для `ForwardIt2`. Подпись не обязательно должна иметь `const &`, но функция не должна изменять объекты, переданные ей.
Требования к типу
-`ForwardIt1, ForwardIt2` должен удовлетворять требованиям LegacyForwardIterator.
-`ForwardIt1, ForwardIt2` должны иметь одинаковый тип значения.

Значение результата

true , если диапазон [first1, last1) является перестановкой диапазона [first2, last2).

Сложность

Не более \(\scriptsize \mathcal{O}(N^2)\)O(N²) применений предиката, или точно \(\scriptsize N\)N, если последовательности уже равны, где \(\scriptsize N\)N является std::distance(first1, last1).

Однако, если ForwardIt1 и ForwardIt2 удовлетворяют требованиям LegacyRandomAccessIterator и std::distance(first1, last1) != std::distance(first2, last2) , не производится никаких применений предиката.

Примечание

Функция std::is_permutation может использоваться для тестирования, а именно для проверки корректности алгоритмов перестановки (например, сортировки, перемешивания, разбиения). Если x это исходный диапазон, а y — переставленный диапазон, то std::is_permutation(x, y) == true означает, что y состоят из "одинаковых" элементов, возможно, находящихся в других позициях.

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

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

Пример

#include <algorithm>
#include <iostream>
 
template<typename Os, typename V>
Os& operator<<(Os& os, V const& v)
{
    os << "{ ";
    for (auto const& 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	генерирует следующую большую лексикографическую перестановку диапазона элементов (шаблон функции)
prev_permutation	генерирует следующую меньшую лексикографическую перестановку диапазона элементов (шаблон функции)
equivalence_relation (C++20)	определяет, что `relation` задаёт отношение эквивалентности (концепция)
ranges::is_permutation (C++20)	определяет, является ли последовательность перестановкой другой последовательности (niebloid)

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