home | help 
std::ranges..._permutation(3)  C++ Standard Libary std::ranges..._permutation(3)

NAME
     std::ranges::is_permutation - std::ranges::is_permutation

Synopsis
	Defined in header <algorithm>
	Call signature
	template< std::forward_iterator I1, std::sentinel_for<I1> S1,

		  std::forward_iterator I2, std::sentinel_for<I2> S2,
		  class Proj1 = std::identity, class Proj2 = std::identity,
		  std::indirect_equivalence_relation<std::projected<I1, Proj1>,
						     std::projected<I2,  Proj2>>
     (since
							 Pred = ranges::equal_to
     (1) C++20)
	>
	constexpr bool
	    is_permutation( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred
	= {},

			    Proj1 proj1 = {}, Proj2 proj2 = {} );
	template< ranges::forward_range R1, ranges::forward_range R2,

		  class Proj1 = std::identity, class Proj2 = std::identity,
		  std::indirect_equivalence_relation<
		      std::projected<ranges::iterator_t<R1>,		 Proj1>,
     (since
		      std::projected<ranges::iterator_t<R2>,		 Proj2>>
     (2) C++20)
			  Pred = ranges::equal_to >
	constexpr bool
	    is_permutation( R1&& r1, R2&& r2, Pred pred = {},

			    Proj1 proj1 = {}, Proj2 proj2 = {} );

	1) Returns true if there exists a permutation of the elements in range
	[first1, last1) that makes the range equal to [first2, last2) (after ap-
     plication 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 sec-
     ond 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	niebloids,  that
     is:

	  *  Explicit  template  argument lists cannot be specified when calling
     any of them.
	  * None of them are visible to argument-dependent lookup.
	  * When any of them are found by normal unqualified lookup as the  name
     to the left
	    of	the  function-call operator, argument-dependent lookup is inhib-
     ited.

	In practice, they may be implemented as function objects, or  with  spe-
     cial compiler
	extensions.

Parameters
	first1, last1 - the first range of the elements
	first2, last2 - the second range of the elements
	r1	      - the first range of the elements
	r2	      - the second range 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 \(\scriptsize \mathcal{O}(N^2)\)O(N^2) applications of the pred-
     icate and
	each  projection, or exactly \(\scriptsize N\)N if the sequences are al-
     ready equal,
	where \(\scriptsize N\)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 equivalence relation.

	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
     struct is_permutation_fn {
	 template<std::forward_iterator I1, std::sentinel_for<I1> S1,
		  std::forward_iterator I2, std::sentinel_for<I2> S2,
		  class Proj1 = std::identity, class Proj2 = std::identity,
		  std::indirect_equivalence_relation<std::projected<I1, Proj1>,
						     std::projected<I2, Proj2>>
							 Pred		       =
     ranges::equal_to>
	 constexpr bool operator()(I1 first1, S1 last1, I2 first2, S2 last2,
				   Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2
     = {}) const
	 {
	     // skip common prefix
	     auto ret = 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 (auto i {first1}; i != last1; ++i)
	     {
		 const auto i_proj {std::invoke(proj1, *i)};
		 auto i_cmp = [&]<typename T>(T&& t)
		 {
		     return std::invoke(pred, i_proj, std::forward<T>(t));
		 };

		 if (i != ranges::find_if(first1, i, i_cmp, proj1))
		     continue; // this *i has been checked

		 if   (const  auto  m  {ranges::count_if(first2,  last2,  i_cmp,
     proj2)};
		     m == 0 or m != ranges::count_if(i, last1, i_cmp, proj1))
		     return false;
	     }
	     return true;
	 }

	 template<ranges::forward_range R1, ranges::forward_range R2,
		  class Proj1 = std::identity, class Proj2 = std::identity,
		  std::indirect_equivalence_relation<
		      std::projected<ranges::iterator_t<R1>, Proj1>,
		      std::projected<ranges::iterator_t<R2>, Proj2>>
			  Pred = ranges::equal_to>
	 constexpr bool operator()(R1&& r1, R2&& r2, Pred pred = {},
				   Proj1 proj1 = {}, Proj2 proj2 = {}) const
	 {
	     return (*this)(ranges::begin(r1), ranges::end(r1),
			    ranges::begin(r2), ranges::end(r2),
			    std::move(pred),		       std::move(proj1),
     std::move(proj2));
	 } };

     inline constexpr is_permutation_fn is_permutation {};

Example
     // Run this code

      #include <algorithm>
      #include <array>
      #include <cmath>
      #include <iostream>
      #include <ranges>

      auto& operator<<(auto& os, std::ranges::forward_range auto const& v)
      {
	  os << "{ ";
	  for (const auto& e : v)
	      os << e << ' ';
	  return os << "}";
      }

      int main()
      {
	  static constexpr auto r1 = {1, 2, 3, 4, 5};
	  static constexpr auto r2 = {3, 5, 4, 1, 2};
	  static constexpr auto r3 = {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 range
		  std::array {'F', 'E', 'C', 'B', 'D'},  // 2nd range
		  [](int x, int y) { return abs(x) == abs(y); }, // predicate
		  [](int x) { return x + 10; }, 	 // projection	for  1st
     range
		  [](char  y)  { return int(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
	ranges::next_permutation generates the next greater lexicographic permu-
     tation of a
	(C++20) 		 range of elements
				 (niebloid)
	ranges::prev_permutation generates the next smaller lexicographic permu-
     tation of a
	(C++20) 		 range of elements
				 (niebloid)
	is_permutation		 determines if a sequence is  a  permutation  of
     another
	(C++11) 		 sequence
				 (function template)
				 generates the next greater lexicographic permu-
     tation of a
	next_permutation	 range of elements
				 (function template)
				 generates the next smaller lexicographic permu-
     tation of a
	prev_permutation	 range of elements
				 (function template)
	equivalence_relation	  specifies  that  a relation imposes an equiva-
     lence relation
	(C++20) 		 (concept)

http://cppreference.com 	   2024.06.10	   std::ranges..._permutation(3)
home | help