Combination Masks
(algo/enumeration/combination.hpp)

• View this file on GitHub
• Last update: 2026-07-07 22:10:04+09:00
• Include: #include "algo/enumeration/combination.hpp"

Overview

This header generates fixed-size subsets as bitmasks. The public namespace is m1une::algo.

UInt must be an unsigned integral type other than bool.

Functions

Function	Description	Complexity
first_combination_mask<UInt>(bit_count, choose)	Returns the smallest mask with choose bits among bit_count bits.	$O(1)$
next_combination_mask(mask, bit_count)	Advances mask to the next mask with the same popcount; returns false when none exists.	$O(1)$
for_each_combination_mask<UInt>(bit_count, choose, f)	Calls f(mask) for every choose-subset of [0, bit_count).	$O(\binom{B}{K})$

Masks are generated in increasing numeric order.

Example

#include "algo/enumeration/combination.hpp"

#include <cstdint>
#include <vector>

int main() {
    std::vector<std::uint64_t> masks;
    m1une::algo::for_each_combination_mask(5, 3, [&](std::uint64_t mask) {
        masks.push_back(mask);
    });
}

Required by

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

Verified with

• verify/algo/enumeration/combination.test.cpp

Code

#ifndef M1UNE_ALGO_ENUMERATION_COMBINATION_HPP
#define M1UNE_ALGO_ENUMERATION_COMBINATION_HPP 1

#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

#endif  // M1UNE_ALGO_ENUMERATION_COMBINATION_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

Back to top page