Enumeration Algorithms All
(algo/enumeration/all.hpp)

• View this file on GitHub
• Last update: 2026-07-25 23:25:14+09:00
• Include: #include "algo/enumeration/all.hpp"

Overview

algo/enumeration/all.hpp includes helpers for traversing combinatorial state spaces. The public namespace is m1une::algo.

Included Headers

Header	Contents
algo/enumeration/gray_code.hpp	Binary-reflected Gray-code encoding, decoding, and enumeration.
algo/enumeration/segtree_range.hpp	Decomposition into maximal aligned segment-tree ranges.
algo/enumeration/submask.hpp	Submask and supermask enumeration helpers.
algo/enumeration/combination.hpp	Fixed-size subset mask generation helpers.
algo/enumeration/permutation_lexicographical_order.hpp	Rank and select permutations in lexicographical order.

Depends on

• Combination Masks (algo/enumeration/combination.hpp)
• Gray Code (algo/enumeration/gray_code.hpp)
• Permutation Lexicographical Order (algo/enumeration/permutation_lexicographical_order.hpp)
• Segment Tree Range Split (algo/enumeration/segtree_range.hpp)
• Submask Enumeration (algo/enumeration/submask.hpp)

Required by

• Algorithms All (algo/all.hpp)

Code

#ifndef M1UNE_ALGO_ENUMERATION_ALL_HPP
#define M1UNE_ALGO_ENUMERATION_ALL_HPP 1

#include "combination.hpp"
#include "gray_code.hpp"
#include "permutation_lexicographical_order.hpp"
#include "segtree_range.hpp"
#include "submask.hpp"

#endif  // M1UNE_ALGO_ENUMERATION_ALL_HPP

#line 1 "algo/enumeration/all.hpp"



#line 1 "algo/enumeration/combination.hpp"



#include <cassert>
#include <concepts>
#include <cstdint>
#include <limits>
#include <type_traits>

namespace m1une {
namespace algo {

namespace internal {

template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
UInt combination_low_bits(int bit_count) {
    constexpr int digits = std::numeric_limits<UInt>::digits;
    assert(0 <= bit_count && bit_count <= digits);
    if (bit_count == digits) return ~UInt(0);
    return (UInt(1) << bit_count) - UInt(1);
}

}  // namespace internal

template <std::unsigned_integral UInt = std::uint64_t>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
UInt first_combination_mask(int bit_count, int choose) {
    constexpr int digits = std::numeric_limits<UInt>::digits;
    assert(0 <= choose && choose <= bit_count && bit_count <= digits);
    if (choose == 0) return UInt(0);
    if (choose == bit_count) return internal::combination_low_bits<UInt>(bit_count);
    return (UInt(1) << choose) - UInt(1);
}

template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
bool next_combination_mask(UInt& mask, int bit_count) {
    const UInt universe = internal::combination_low_bits<UInt>(bit_count);
    assert((mask & ~universe) == 0);
    if (mask == 0) return false;

    const UInt lowest = mask & (~mask + UInt(1));
    const UInt ripple = mask + lowest;
    if (ripple == 0 || (ripple & ~universe) != 0) return false;

    const UInt next = (((ripple ^ mask) >> 2) / lowest) | ripple;
    if ((next & ~universe) != 0) return false;
    mask = next;
    return true;
}

template <std::unsigned_integral UInt = std::uint64_t, class F>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
void for_each_combination_mask(int bit_count, int choose, F f) {
    constexpr int digits = std::numeric_limits<UInt>::digits;
    assert(0 <= choose && choose <= bit_count && bit_count <= digits);
    UInt mask = first_combination_mask<UInt>(bit_count, choose);
    while (true) {
        f(mask);
        if (!next_combination_mask(mask, bit_count)) break;
    }
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/enumeration/gray_code.hpp"



#line 6 "algo/enumeration/gray_code.hpp"
#include <cstddef>
#line 10 "algo/enumeration/gray_code.hpp"
#include <vector>

namespace m1une {
namespace algo {

// Converts a binary value to its binary-reflected Gray code.
template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
constexpr UInt gray_encode(UInt value) noexcept {
    return value ^ (value >> 1);
}

// Converts a binary-reflected Gray code to the corresponding binary value.
template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
constexpr UInt gray_decode(UInt code) noexcept {
    for (int shift = 1; shift < std::numeric_limits<UInt>::digits;
         shift <<= 1) {
        code ^= code >> shift;
    }
    return code;
}

// Returns all bit_count-bit binary-reflected Gray codes in traversal order.
template <std::unsigned_integral UInt = std::uint64_t>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
std::vector<UInt> gray_code_sequence(int bit_count) {
    constexpr int uint_digits = std::numeric_limits<UInt>::digits;
    constexpr int size_digits = std::numeric_limits<std::size_t>::digits;
    assert(0 <= bit_count);
    assert(bit_count <= uint_digits);
    assert(bit_count < size_digits);
    if (bit_count < 0 || uint_digits < bit_count || size_digits <= bit_count) {
        return {};
    }

    const std::size_t size = std::size_t(1) << bit_count;
    std::vector<UInt> result(size);
    for (std::size_t index = 0; index < size; ++index) {
        result[index] = gray_encode(static_cast<UInt>(index));
    }
    return result;
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/enumeration/permutation_lexicographical_order.hpp"



#line 8 "algo/enumeration/permutation_lexicographical_order.hpp"
#include <optional>
#line 10 "algo/enumeration/permutation_lexicographical_order.hpp"
#include <utility>
#line 12 "algo/enumeration/permutation_lexicographical_order.hpp"

namespace m1une {
namespace algo {

namespace internal {

struct PermutationOrderFenwick {
    std::vector<int> data;

    explicit PermutationOrderFenwick(int size) : data(size + 1) {}

    void add(int index, int value) {
        for (index++; index < int(data.size()); index += index & -index) {
            data[index] += value;
        }
    }

    int prefix_sum(int right) const {
        int result = 0;
        for (; 0 < right; right -= right & -right) result += data[right];
        return result;
    }

    int kth(int order) const {
        int index = 0;
        int accumulated = 0;
        int step = 1;
        while (step < int(data.size())) step <<= 1;
        for (; 0 < step; step >>= 1) {
            const int next = index + step;
            if (next < int(data.size()) &&
                accumulated + data[next] <= order) {
                index = next;
                accumulated += data[next];
            }
        }
        return index;
    }
};

}  // namespace internal

// Returns the zero-based lexicographical rank of a permutation of [0, n).
// Returns nullopt when the sequence is invalid or the rank does not fit in UInt.
template <
    std::unsigned_integral UInt = std::uint64_t,
    class Permutation
>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
std::optional<UInt> checked_permutation_lexicographical_rank(
    const Permutation& permutation
) {
    const int size = int(permutation.size());
    internal::PermutationOrderFenwick fenwick(size);
    for (int value = 0; value < size; value++) fenwick.add(value, 1);

    UInt rank = 0;
    constexpr UInt limit = std::numeric_limits<UInt>::max();
    for (int index = 0; index < size; index++) {
        const auto& value_reference = permutation[index];
        using Value = std::remove_cvref_t<decltype(value_reference)>;
        static_assert(std::integral<Value>);
        static_assert(!std::same_as<Value, bool>);

        if (std::cmp_less(value_reference, 0) ||
            std::cmp_greater_equal(value_reference, size)) {
            return std::nullopt;
        }
        const int value = int(value_reference);
        if (fenwick.prefix_sum(value + 1) == fenwick.prefix_sum(value)) {
            return std::nullopt;
        }

        const std::uintmax_t smaller = fenwick.prefix_sum(value);
        const std::uintmax_t remaining = size - index;
        if (smaller > std::uintmax_t(limit) ||
            std::uintmax_t(rank) >
                (std::uintmax_t(limit) - smaller) / remaining) {
            return std::nullopt;
        }
        rank = UInt(std::uintmax_t(rank) * remaining + smaller);
        fenwick.add(value, -1);
    }
    return rank;
}

// Every value must occur exactly once in [0, n), and the rank must fit in UInt.
template <
    std::unsigned_integral UInt = std::uint64_t,
    class Permutation
>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
UInt permutation_lexicographical_rank(const Permutation& permutation) {
    const std::optional<UInt> result =
        checked_permutation_lexicographical_rank<UInt>(permutation);
    assert(result.has_value());
    return result.value_or(UInt(0));
}

// Returns the permutation of [0, size) with the given zero-based rank.
// Returns nullopt when size is negative or rank is at least size factorial.
template <std::unsigned_integral UInt = std::uint64_t>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
std::optional<std::vector<int>> checked_kth_lexicographical_permutation(
    int size,
    UInt rank
) {
    if (size < 0) return std::nullopt;

    std::vector<int> lehmer_code(size);
    UInt remaining_rank = rank;
    for (int base = 1; base <= size && remaining_rank != 0; base++) {
        lehmer_code[size - base] = int(remaining_rank % UInt(base));
        remaining_rank /= UInt(base);
    }
    if (remaining_rank != 0) return std::nullopt;

    internal::PermutationOrderFenwick fenwick(size);
    for (int value = 0; value < size; value++) fenwick.add(value, 1);

    std::vector<int> permutation(size);
    for (int index = 0; index < size; index++) {
        const int value = fenwick.kth(lehmer_code[index]);
        permutation[index] = value;
        fenwick.add(value, -1);
    }
    return permutation;
}

// Rank must be less than size factorial.
template <std::unsigned_integral UInt = std::uint64_t>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
std::vector<int> kth_lexicographical_permutation(int size, UInt rank) {
    std::optional<std::vector<int>> result =
        checked_kth_lexicographical_permutation(size, rank);
    assert(result.has_value());
    return result.value_or(std::vector<int>());
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/enumeration/segtree_range.hpp"



#include <bit>
#line 10 "algo/enumeration/segtree_range.hpp"

namespace m1une {
namespace algo {

// Splits [left, right) into maximal segment-tree ranges from left to right.
template <std::integral Int>
requires(!std::same_as<std::remove_cv_t<Int>, bool>)
std::vector<std::pair<Int, Int>> split_segtree_range(Int left, Int right) {
    if constexpr (std::signed_integral<Int>) assert(Int(0) <= left);
    assert(left <= right);
    if constexpr (std::signed_integral<Int>) {
        if (left < 0) return {};
    }
    if (right < left) return {};

    using UInt = std::make_unsigned_t<Int>;
    UInt position = static_cast<UInt>(left);
    const UInt end = static_cast<UInt>(right);
    std::vector<std::pair<Int, Int>> result;
    if (position == end) return result;
    result.reserve(2 * std::bit_width(end - position));

    while (position < end) {
        UInt length = std::bit_floor(end - position);
        if (position != 0) {
            const UInt alignment = position & (~position + UInt(1));
            if (alignment < length) length = alignment;
        }
        const UInt next = position + length;
        result.emplace_back(
            static_cast<Int>(position), static_cast<Int>(next)
        );
        position = next;
    }
    return result;
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/enumeration/submask.hpp"



#line 8 "algo/enumeration/submask.hpp"

namespace m1une {
namespace algo {

namespace internal {

template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
UInt submask_low_bits(int bit_count) {
    constexpr int digits = std::numeric_limits<UInt>::digits;
    assert(0 <= bit_count && bit_count <= digits);
    if (bit_count == digits) return ~UInt(0);
    return (UInt(1) << bit_count) - UInt(1);
}

}  // namespace internal

template <std::unsigned_integral UInt, class F>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
void for_each_submask(UInt mask, F f) {
    UInt submask = mask;
    while (true) {
        f(submask);
        if (submask == 0) break;
        submask = (submask - 1) & mask;
    }
}

template <std::unsigned_integral UInt, class F>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
void for_each_nonzero_submask(UInt mask, F f) {
    for (UInt submask = mask; submask != 0; submask = (submask - 1) & mask) {
        f(submask);
    }
}

template <std::unsigned_integral UInt, class F>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
void for_each_supermask(UInt mask, int bit_count, F f) {
    const UInt universe = internal::submask_low_bits<UInt>(bit_count);
    assert((mask & ~universe) == 0);
    const UInt free_bits = universe ^ mask;
    for_each_submask(free_bits, [&](UInt added_bits) {
        f(mask | added_bits);
    });
}

}  // namespace algo
}  // namespace m1une


#line 9 "algo/enumeration/all.hpp"

Back to top page