Przejdź do głównej zawartości

std::ranges::is_permutation() algorithm

// (1)
constexpr bool
is_partitioned( I first, S last, Pred pred, Proj proj = {} );

// (2)
constexpr bool
is_partitioned( R&& r, Pred pred, Proj proj = {} );

The type of arguments are generic and have the following constraints:

  • I - std::input_iterator
  • S - std::sentinel_for<I>
  • R - std::ranges::input_range
  • Pred:
    • (1) - std::indirect_unary_predicate<std::projected<I, Proj>>
    • (2) - std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>, Proj>>
  • Proj - (none)

The Proj template argument has a default type std::identity for all overloads.

  • (1) Returns true if there exists a permutation 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 niebloids.

Parameters

first1
last1

The first range of elements to process.

r

The first range of elements to process.

first2
last2

The second range of elements to process.

r

The second range of elements to process.

pred

The predicate to apply to the projected elemenets.

proj

The projection to apply to the elements.

Return value

true if the range [first1; last1) is a permutation of the range [first2; last2).

Complexity

Given N is ranges::distance(first1, last1).

At most O(N2) applications of the predicate and each projection, or exactly N if the sequences are already equal,

However if ranges::distance(first1, last1) != ranges::distance(first2, last2), no applications of the predicate and projections are made.

Exceptions

(none)

Possible implementation

is_permutation(1) and is_permutation(2)
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 {};

Notes

The permutation relation is an equivalence relation.

The ranges::is_permutation can be used in testing, namely to check the correctness of rearranging algorithms (e.g. sorting, shuffling, partitioning).

If x is an original range and y is a permuted range then ranges::is_permutation(x, y) == true means that y consist of "the same" elements, maybe staying at other positions.

Examples

Main.cpp
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <ranges>

auto& operator<<(auto& os, std::ranges::forward_range auto const& v)
{
os << "{ ";
for (auto const& 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';
}
Possible 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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.

std::ranges::is_permutation() algorithm

// (1)
constexpr bool
is_partitioned( I first, S last, Pred pred, Proj proj = {} );

// (2)
constexpr bool
is_partitioned( R&& r, Pred pred, Proj proj = {} );

The type of arguments are generic and have the following constraints:

  • I - std::input_iterator
  • S - std::sentinel_for<I>
  • R - std::ranges::input_range
  • Pred:
    • (1) - std::indirect_unary_predicate<std::projected<I, Proj>>
    • (2) - std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>, Proj>>
  • Proj - (none)

The Proj template argument has a default type std::identity for all overloads.

  • (1) Returns true if there exists a permutation 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 niebloids.

Parameters

first1
last1

The first range of elements to process.

r

The first range of elements to process.

first2
last2

The second range of elements to process.

r

The second range of elements to process.

pred

The predicate to apply to the projected elemenets.

proj

The projection to apply to the elements.

Return value

true if the range [first1; last1) is a permutation of the range [first2; last2).

Complexity

Given N is ranges::distance(first1, last1).

At most O(N2) applications of the predicate and each projection, or exactly N if the sequences are already equal,

However if ranges::distance(first1, last1) != ranges::distance(first2, last2), no applications of the predicate and projections are made.

Exceptions

(none)

Possible implementation

is_permutation(1) and is_permutation(2)
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 {};

Notes

The permutation relation is an equivalence relation.

The ranges::is_permutation can be used in testing, namely to check the correctness of rearranging algorithms (e.g. sorting, shuffling, partitioning).

If x is an original range and y is a permuted range then ranges::is_permutation(x, y) == true means that y consist of "the same" elements, maybe staying at other positions.

Examples

Main.cpp
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <ranges>

auto& operator<<(auto& os, std::ranges::forward_range auto const& v)
{
os << "{ ";
for (auto const& 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';
}
Possible 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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.