numeric/next_combination.hpp

View this file on GitHub
Last update: 2025-12-14 01:45:16+09:00
Include: #include "numeric/next_combination.hpp"

Depends on

Required by

Verified with

verify/aizu-online-judge/itp1_1_a/0001.test.cpp

Code

#pragma once


#include <iterator>
#include <ranges>
#include <concepts>
#include <algorithm>


#include "internal/dev_env.hpp"
#include "internal/types.hpp"


namespace uni {


template<class Size = internal::size_t>
struct next_combination {
    using size_type = Size;

  private:
    size_type _size;

  public:
    next_combination(const size_type size) : _size(size) {};

    auto size() noexcept(NO_EXCEPT) { return this->_size; }

    template<std::ranges::bidirectional_range R>
    auto operator()(R&& range) const noexcept(NO_EXCEPT) { return this->operator()(ALL(range)); }

    template<std::bidirectional_iterator I, std::sentinel_for<I> S>
    auto operator()(I first, S last) const noexcept(NO_EXCEPT) {
        auto subset = std::ranges::next(first, this->size());

        if(first == last || first == subset || last == subset) return false;

        auto src = subset;
        while (first != src) {
            --src;

            if (*src < *std::ranges::prev(last)) {
                auto dest = subset;
                while (*src >= *dest) ++dest;

                std::ranges::iter_swap(src, dest);
                std::ranges::rotate(std::ranges::next(src), std::ranges::next(dest), last);
                std::ranges::rotate(subset, std::ranges::next(subset, std::ranges::distance(dest, last) - 1), last);

                return true;
            }
        }

        std::ranges::rotate(first, subset, last);

        return false;
    }
};


}  // namespace uni

#line 2 "numeric/next_combination.hpp"


#include <iterator>
#include <ranges>
#include <concepts>
#include <algorithm>


#line 2 "internal/dev_env.hpp"


#ifdef LOCAL_JUDGE
    inline constexpr bool DEV_ENV = true;
    inline constexpr bool NO_EXCEPT = false;
#else
    inline constexpr bool DEV_ENV = false;
    inline constexpr bool NO_EXCEPT = true;
#endif // LOCAL_JUDGE


#if __cplusplus >= 202100L
    #define CPP20 true
    #define CPP23 true
#elif __cplusplus >= 202002L
    #define CPP20 true
    #define CPP23 false
#else
    #define CPP20 false
    #define CPP23 false
#endif
#line 2 "internal/types.hpp"

#include <cstdint>

namespace uni {

namespace internal {


using size_t = std::int64_t;

using int128_t = __int128_t;
using uint128_t = __uint128_t;


} // namesapce internal

} // namespace uni
#line 12 "numeric/next_combination.hpp"


namespace uni {


template<class Size = internal::size_t>
struct next_combination {
    using size_type = Size;

  private:
    size_type _size;

  public:
    next_combination(const size_type size) : _size(size) {};

    auto size() noexcept(NO_EXCEPT) { return this->_size; }

    template<std::ranges::bidirectional_range R>
    auto operator()(R&& range) const noexcept(NO_EXCEPT) { return this->operator()(ALL(range)); }

    template<std::bidirectional_iterator I, std::sentinel_for<I> S>
    auto operator()(I first, S last) const noexcept(NO_EXCEPT) {
        auto subset = std::ranges::next(first, this->size());

        if(first == last || first == subset || last == subset) return false;

        auto src = subset;
        while (first != src) {
            --src;

            if (*src < *std::ranges::prev(last)) {
                auto dest = subset;
                while (*src >= *dest) ++dest;

                std::ranges::iter_swap(src, dest);
                std::ranges::rotate(std::ranges::next(src), std::ranges::next(dest), last);
                std::ranges::rotate(subset, std::ranges::next(subset, std::ranges::distance(dest, last) - 1), last);

                return true;
            }
        }

        std::ranges::rotate(first, subset, last);

        return false;
    }
};


}  // namespace uni