std::ranges::prev_permutation() algorithm

od C++20

Simplified

// (1)
constexpr prev_permutation_result<I>
    prev_permutation( I first, S last, Comp comp = {}, Proj proj = {} );

// (2)
constexpr prev_permutation_result<ranges::borrowed_iterator_t<R>>
    prev_permutation( R&& r, Comp comp = {}, Proj proj = {} );

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

• I - std::bidirectional_iterator
• S - std::sentinel_for<I>
• R - std::bidirectional_range
• Comp:
  • (1) - std::sortable<I, Comp, Proj>
  • (2) - std::sortable<ranges::iterator_t<R>, Comp, Proj>
• Proj - (none)

The Proj and Comp template arguments have default types of std::identity and ranges::less for all overloads.

Detailed

// (1)
template<
  std::bidirectional_iterator I,
  std::sentinel_for<I> S,
  class Comp = ranges::less,
  class Proj = std::identity
>
  requires std::sortable<I, Comp, Proj>
constexpr prev_permutation_result<I>
    prev_permutation( I first, S last, Comp comp = {}, Proj proj = {} );

// (2)
template<
  ranges::bidirectional_range R,
  class Comp = ranges::less,
  class Proj = std::identity
>
  requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr prev_permutation_result<ranges::borrowed_iterator_t<R>>
    prev_permutation( R&& r, Comp comp = {}, Proj proj = {} );

• (1) Transforms the range [first; last) into the previous permutation, where the set of all permutations is ordered lexicographically with respect to binary comparison function object comp and projection function object proj. Returns:

  • { last, true } if such a "prev permutation" exists
  • { last, false } and transforms the range into the (lexicographically) last permutation, as if by:

  ranges::sort(first, last, comp, proj);
  ranges::reverse(first, last);

• (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 range of elements to permute.
r	The range of elements to permute.
comp	Comparison function object which returns true if the first argument is less than the second.
proj	The projection to apply to the elements.

Return value

• (1) ranges::prev_permutation_result<I>{ last, true } if the new permutation is lexicographically less than the old one. ranges::prev_permutation_result<I>{ last, false } if the first permutation was reached and the range was reset to the last permutation.

• (2) same as (1) except that the return type is ranges::prev_permutation_result<ranges::borrowed_iterator_t<R>>.

Complexity

Given N as ranges::distance(first, last):

• (1) At most N / 2 swaps.
• (2) At most ranges::distance(r) swaps.

Averaged over the entire sequence of permutations, typical implementations use about 3 comparisons and 1.5 swaps per call.

Exceptions

Any exceptions thrown from iterator operations or the element swap.

Possible implementation

Implementations (e.g. MSVC STL may enable vectorization when the iterator type satisfies contiguous_iterator and swapping its value type calls neither non-trivial special member function nor ADL-found swap.

prev_permutation(1) and prev_permutation(2)

struct prev_permutation_fn
{
    template <std::bidirectional_iterator I, std::sentinel_for<I> S,
              class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr ranges::prev_permutation_result<I>
        operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        // check that the sequence has at least two elements
        if (first == last)
            return {std::move(first), false};
        auto i {first};
        ++i;
        if (i == last)
            return {std::move(i), false};
        auto i_last {ranges::next(first, last)};
        i = i_last;
        --i;
        // main "permutating" loop
        for (;;)
        {
            auto i1 {i};
            --i;
            if (std::invoke(comp, std::invoke(proj, *i1), std::invoke(proj, *i)))
            {
                auto j {i_last};
                while (!std::invoke(comp, std::invoke(proj, *--j), std::invoke(proj, *i)))
                    ;
                ranges::iter_swap(i, j);
                ranges::reverse(i1, last);
                return {std::move(i_last), true};
            }
            // permutation "space" is exhausted
            if (i == first)
            {
                ranges::reverse(first, last);
                return {std::move(i_last), false};
            }
        }
    }

    template<ranges::bidirectional_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::prev_permutation_result<ranges::borrowed_iterator_t<R>>
        operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r),
                       std::move(comp), std::move(proj));
    }
};

inline constexpr prev_permutation_fn prev_permutation {};

Examples

Main.cpp

#include <algorithm>
#include <array>
#include <compare>
#include <functional>
#include <iostream>
#include <string>

struct S
{
    char c {};
    int i {};
    auto operator<=>(const S&) const = default;
    friend std::ostream& operator<<(std::ostream& os, const S& s)
    {
        return os << "{'" << s.c << "', " << s.i << "}";
    }
};

auto print = [](auto const& v, char term = ' ')
{
    std::cout << "{ ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '}' << term;
};

int main()
{
    std::cout << "Generate all permutations (iterators case):\n";
    std::string s {"cba"};
    do print(s);
    while (std::ranges::prev_permutation(s.begin(), s.end()).found);

    std::cout << "\nGenerate all permutations (range case):\n";
    std::array a {'c', 'b', 'a'};
    do print(a);
    while (std::ranges::prev_permutation(a).found);

    std::cout << "\nGenerate all permutations using comparator:\n";
    using namespace std::literals;
    std::array z { "▁"s, "▄"s, "█"s };
    do print(z);
    while (std::ranges::prev_permutation(z, std::greater()).found);

    std::cout << "\nGenerate all permutations using projection:\n";
    std::array<S, 3> r { S{'C',1}, S{'B',2}, S{'A',3} };
    do print(r, '\n');
    while (std::ranges::prev_permutation(r, {}, &S::c).found);
}

Possible Output

Generate all permutations (iterators case):
{ c b a } { c a b } { b c a } { b a c } { a c b } { a b c }
Generate all permutations (range case):
{ c b a } { c a b } { b c a } { b a c } { a c b } { a b c }
Generate all permutations using comparator:
{ ▁ ▄ █ } { ▁ █ ▄ } { ▄ ▁ █ } { ▄ █ ▁ } { █ ▁ ▄ } { █ ▄ ▁ }
Generate all permutations using projection:
{ {'C', 1} {'B', 2} {'A', 3} }
{ {'C', 1} {'A', 3} {'B', 2} }
{ {'B', 2} {'C', 1} {'A', 3} }
{ {'B', 2} {'A', 3} {'C', 1} }
{ {'A', 3} {'C', 1} {'B', 2} }
{ {'A', 3} {'B', 2} {'C', 1} }