std::ranges..._permutation(3)

std::ranges..._permutation(3) ✨💅

Okay so this is from the C++ Standard Libary manual (yes, “Libary” is literally how the header spells it, and we are choosing peace 💀), and the page title is std::ranges..._permutation(3). The actual main character here is std::ranges::is_permutation, and she is lowkey iconic.

💖 NAME 💖

std::ranges::is_permutation — std::ranges::is_permutation. That’s the whole name, bestie, we’re not doing extra.

🌸 Synopsis 🌸

Defined in header

<algorithm>

Call signature

Overload (1), since C++20:

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
    is_permutation( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                    Proj1 proj1 = {}, Proj2 proj2 = {} );

Overload (2), since C++20:

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
    is_permutation( R1&& r1, R2&& r2, Pred pred = {},
                    Proj1 proj1 = {}, Proj2 proj2 = {} );

So (1) returns true if there exists a permutation of the elements in range [first1, last1) that makes the range equal to [first2, last2) — after applying the corresponding projections Proj1, Proj2, and using the binary predicate Pred as a comparator. Otherwise it returns false. No cap.

And (2) is the same as (1), but it 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, 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 inhibited.

In practice, they may be implemented as function objects, or with special compiler extensions. iykyk ✨

🫶 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). That’s the vibe check, and she either passes or she doesn’t 💅

🔥 Complexity 🔥

At most O(N^2) applications of the predicate and each projection, or exactly N if the sequences are already equal, where N is ranges::distance(first1, last1). But if ranges::distance(first1, last1) != ranges::distance(first2, last2), no applications of the predicate and projections are made. Zero. None. The efficiency ate.

🦋 Notes 🦋

The permutation relation is an equivalence relation. Periodt.

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 consists of “the same” elements (maybe permuted) as p. That’s the whole point, bestie.

🧚 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 (C++20) (niebloid) — generates the next greater lexicographic permutation of a range of elements
• ranges::prev_permutation (C++20) (niebloid) — generates the next smaller lexicographic permutation of a range of elements
• is_permutation (C++11) (function template) — determines if a sequence is a permutation of another sequence
• next_permutation (function template) — generates the next greater lexicographic permutation of a range of elements
• prev_permutation (function template) — generates the next smaller lexicographic permutation of a range of elements
• equivalence_relation (C++20) (concept) — specifies that a relation imposes an equivalence relation

---

Signed, sealed, delivered, no cap: http://cppreference.com · 2024.06.10 · std::ranges..._permutation(3) 🌈✨💖