std::is_permutation

 

C++

Язык

Заголовочные файлы

Концепты

Поддержка языка

Ошибка

Утилиты

Строки

Контейнеры

Алгоритмы

Итераторы

Работа с числами

Ввод/вывод

Локализация

Регулярные выражения(C++11)

Атомарные операции(C++11)

Потоки(C++11)

Файловая система(C++17)

Технические спецификации

 

Алгоритмы

Функции
Немодифицирующие линейные операции
all_ofany_ofnone_of Шаблон:lines for_each countcount_if mismatch equal	findfind_iffind_if_not Шаблон:lines find_end find_first_of adjacent_find search search_n
Модифицирующие линейные операции
copycopy_if Шаблон:lines copy_n Шаблон:lines copy_backward move Шаблон:lines move_backward Шаблон:lines fill fill_n transform generate generate_n removeremove_if remove_copyremove_copy_if	replacereplace_if replace_copyreplace_copy_if swap swap_ranges iter_swap reverse reverse_copy rotate rotate_copy random_shuffleshuffle Шаблон:lines unique unique_copy
Разделение
is_partitioned Шаблон:lines partition partition_copy Шаблон:lines	stable_partition partition_point Шаблон:lines
Сортировка (на отсортированных промежутках)
is_sorted Шаблон:lines is_sorted_until Шаблон:lines sort	partial_sort partial_sort_copy stable_sort nth_element
Бинарный поиск (на отсортированных промежутках)
lower_bound upper_bound	binary_search equal_range
Множества (на отсортированных промежутках)
merge inplace_merge includes	set_difference set_intersection set_symmetric_difference set_union
Куча
is_heap is_heap_until Шаблон:lines make_heap	push_heap pop_heap sort_heap
Минимум/максимум
max max_element min min_element minmax Шаблон:lines minmax_element Шаблон:lines	lexicographical_compare is_permutation Шаблон:lines next_permutation prev_permutation
Числовые операции
iota Шаблон:lines accumulate inner_product	adjacent_difference partial_sum
Библиотека C
qsort	bsearch

 

Defined in header <algorithm>
template<class ForwardIt1, class ForwardIt2 > bool is_permutation( ForwardIt1 first, ForwardIt1 last,                      ForwardIt2 d_first );	(1)	(начиная с C++11)
template<class ForwardIt1, class ForwardIt2, class BinaryPredicate > bool is_permutation( ForwardIt1 first, ForwardIt1 last,                      ForwardIt2 d_first, BinaryPredicate p );	(2)	(начиная с C++11)

Возврат true, если существует перестановка элементов в диапазоне [first1, last1), что делает этот диапазон равный диапазоне начиная с d_first. Первый вариант используется operator== за равноправие, вторая версия использует бинарный p предикат

Оригинал:

Returns true if there exists a permutation of the elements in the range [first1, last1) that makes that range equal to the range beginning at d_first. The first version uses operator== for equality, the second version uses the binary predicate p

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

Параметры

first, last	—	диапазон элементов для сравнения Оригинал: the range of elements to compare Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
d_first	—	В начале второго диапазона для сравнения Оригинал: the beginning of the second range to compare Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
p	—	бинарный предикат, который возвращает ​true если элементы следует считать равными. Определение функции предиката должно быть эквивалентно следующему:  bool pred(const Type1 &a, const Type2 &b); Определение не должно обязательно содержать const&, но функция не должна модифицировать принимаемые объекты. Типы Type1 и Type2 должны быть таковы, что объекты типов ForwardIt1 и ForwardIt2 могут быть разыменованы и затем неявно преобразованы в Type1 и Type2 соответственно. ​
Требования к типам
- ForwardIt1, ForwardIt2 должен соответствовать требованиям ForwardIterator.

Возвращаемое значение

true, если диапазон [first, last) является перестановкой диапазоне начиная с d_first.

Оригинал:

true if the range [first, last) is a permutation of the range beginning at d_first.

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

Сложность

В большинстве O(N²) применения предиката, или точно N если последовательности уже равны, где N=std::distance(first, last).

Оригинал:

At most O(N²) applications of the predicate, or exactly N if the sequences are already equal, where N=std::distance(first, last).

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

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

template<class ForwardIt1, class ForwardIt2>bool is_permutation(ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first){// skip common prefixstd::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 = d_first;std::advance(d_last, std::distance(first, last));for(ForwardIt1 i = first; i != last;++i){if(i !=std::find(first, i, *i))continue;// already counted this *i   auto m =std::count(d_first, d_last, *i);if(m==0||std::count(i, last, *i)!= m){returnfalse;}}}returntrue;}

Пример

Запустить этот код

#include <algorithm>#include <vector>#include <iostream>int main(){std::vector<int> v1{1,2,3,4,5};std::vector<int> v2{3,5,4,1,2};std::cout<<"3,5,4,1,2 is a permutation of 1,2,3,4,5? "<<std::boolalpha<< std::is_permutation(v1.begin(), v1.end(), v2.begin())<<'\n';   std::vector<int> v3{3,5,4,1,1};std::cout<<"3,5,4,1,1 is a permutation of 1,2,3,4,5? "<<std::boolalpha<< 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	generates the next smaller lexicographic permutation of a range of elements (шаблон функции)