Defined in header
Call signature
template<std::forward_iteratorI1,std::sentinel_for<I1>S1,std::forward_iteratorI2,std::sentinel_for<I2>S2,classProj1=std::identity,classProj2=std::identity,std::indirect_equivalence_relation<std::projected<I1,Proj1>,std::projected<I2,Proj2>>Pred=ranges::equal_to>constexprboolis_permutation(I1first1,S1last1,I2first2,S2last2,Predpred={},Proj1proj1={},Proj2proj2={}); (1) (since C++20)template<ranges::forward_rangeR1,ranges::forward_rangeR2,classProj1=std::identity,classProj2=std::identity,std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R1>,Proj1>,std::projected<ranges::iterator_t<R2>,Proj2>>Pred=ranges::equal_to>constexprboolis_permutation(R1&&r1,R2&&r2,Predpred={},Proj1proj1={},Proj2proj2={}); (2) (since C++20)1) Returns true if there exists a
of the elements in range [first1, last1) that makes the range equal to [first2, last2) (after application of corresponding projections Proj1, Proj2, and using the binary predicate Pred as a comparator). Otherwise returns false.
2) Same as (1), but uses r1 as the first source range and r2 as the second source range, as if using ranges::begin(r1) as first1, ranges::end(r1) as last1, ranges::begin(r2) as first2, and ranges::end(r2) as last2.
The function-like entities described on this page are
(informally known as niebloids), that is:
Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to
.
When any of them are found by
as the name to the left of the function-call operator,
is inhibited.
Parameters
first1, last1 - the iterator-sentinel pair defining the first
of elements first2, last2 - the iterator-sentinel pair defining the second
of elements r1 - the first
of the elements r2 - the second
of the elements pred - predicate to apply to the projected elements proj1 - projection to apply to the elements in the first range proj2 - projection to apply to the elements in the second range Return value
true if the range [first1, last1) is a permutation of the range [first2, last2).
Complexity
At most O(N2) applications of the predicate and each projection, or exactly N if the sequences are already equal, where N is ranges::distance(first1,last1). However if ranges::distance(first1,last1)!=ranges::distance(first2,last2), no applications of the predicate and projections are made.
Notes
The permutation relation is an
.
The ranges::is_permutation can be used in testing, e.g. to check the correctness of rearranging algorithms such as sorting, shuffling, partitioning. If p is an original sequence and q is a "mutated" sequence, then ranges::is_permutation(p,q)==true means that q consist of "the same" elements (maybe permuted) as p.
Possible implementation
structis_permutation_fn{template<std::forward_iteratorI1,std::sentinel_for<I1>S1,std::forward_iteratorI2,std::sentinel_for<I2>S2,classProj1=std::identity,classProj2=std::identity,std::indirect_equivalence_relation<std::projected<I1,Proj1>,std::projected<I2,Proj2>>Pred=ranges::equal_to>constexprbooloperator()(I1first1,S1last1,I2first2,S2last2,Predpred={},Proj1proj1={},Proj2proj2={})const{// skip common prefixautoret=std::ranges::mismatch(first1,last1,first2,last2,std::ref(pred),std::ref(proj1),std::ref(proj2));first1=ret.in1,first2=ret.in2;// iterate over the rest, counting how many times each element// from [first1, last1) appears in [first2, last2)for(autoi{first1};i!=last1;++i){constautoi_proj{std::invoke(proj1,*i)};autoi_cmp=[&]<typenameT>(T&&t){returnstd::invoke(pred,i_proj,std::forward<T>(t));};if(i!=ranges::find_if(first1,i,i_cmp,proj1))continue;// this *i has been checkedif(constautom{ranges::count_if(first2,last2,i_cmp,proj2)};m==0orm!=ranges::count_if(i,last1,i_cmp,proj1))returnfalse;}returntrue;}template<ranges::forward_rangeR1,ranges::forward_rangeR2,classProj1=std::identity,classProj2=std::identity,std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R1>,Proj1>,std::projected<ranges::iterator_t<R2>,Proj2>>Pred=ranges::equal_to>constexprbooloperator()(R1&&r1,R2&&r2,Predpred={},Proj1proj1={},Proj2proj2={})const{return(*this)(ranges::begin(r1),ranges::end(r1),ranges::begin(r2),ranges::end(r2),std::move(pred),std::move(proj1),std::move(proj2));}};inlineconstexpris_permutation_fnis_permutation{};Example
Run this code
#include<algorithm>#include<array>#include<cmath>#include<iostream>#include<ranges>auto&operator<<(auto&os,std::ranges::forward_rangeautoconst&v){os<<"{ ";for(constauto&e:v)os<<e<<' ';returnos<<"}";}intmain(){staticconstexprautor1={1,2,3,4,5};staticconstexprautor2={3,5,4,1,2};staticconstexprautor3={3,5,4,1,1};static_assert(std::ranges::is_permutation(r1,r1)&&std::ranges::is_permutation(r1,r2)&&std::ranges::is_permutation(r2,r1)&&std::ranges::is_permutation(r1.begin(),r1.end(),r2.begin(),r2.end()));std::cout<<std::boolalpha<<"is_permutation("<<r1<<", "<<r2<<"): "<<std::ranges::is_permutation(r1,r2)<<'\n'<<"is_permutation("<<r1<<", "<<r3<<"): "<<std::ranges::is_permutation(r1,r3)<<'\n'<<"is_permutation with custom predicate and projections: "<<std::ranges::is_permutation(std::array{-14,-11,-13,-15,-12},// 1st rangestd::array{'F','E','C','B','D'},// 2nd range[](intx,inty){returnabs(x)==abs(y);},// predicate[](intx){returnx+10;},// projection for 1st range[](chary){returnint(y-'A');})// projection for 2nd range<<'\n';}Output:
is_permutation({ 1 2 3 4 5 }, { 3 5 4 1 2 }): true is_permutation({ 1 2 3 4 5 }, { 3 5 4 1 1 }): false is_permutation with custom predicate and projections: true See also
(C++20)
generates the next greater lexicographic permutation of a range of elements
(algorithm function object)
(C++20)
generates the next smaller lexicographic permutation of a range of elements
(algorithm function object)
(C++11)
determines if a sequence is a permutation of another sequence
(function template)
generates the next greater lexicographic permutation of a range of elements
(function template & algorithm function object)
(C++20)
generates the next smaller lexicographic permutation of a range of elements
(function template & algorithm function object)
(C++20)
(C++20)
specifies that a
imposes an equivalence relation
(concept)