如何用C++17+模板元编程编译时生成N元布尔组合列表？

核心实现 #

#include <tuple>
#include <array>
#include <utility>
#include <algorithm>

// 递归终止条件：N=0时返回包含空元组的数组
template <>
constexpr auto boolean_combinations<0>() {
    return std::array<std::tuple<>, 1>{};
}

// 递归生成N长度的布尔组合
template <std::size_t N>
constexpr auto boolean_combinations() {
    // 获取N-1长度的所有组合
    const auto prev_combinations = boolean_combinations<N-1>();
    const auto prev_size = prev_combinations.size();

    // 推导临时数组的元素类型
    using PrevTuple = typename decltype(prev_combinations)::value_type;
    using ResultTuple = decltype(std::tuple_cat(std::make_tuple(true), std::declval<PrevTuple>()));
    
    std::array<ResultTuple, prev_size> with_true;
    std::array<ResultTuple, prev_size> with_false;

    // 填充追加true的数组
    for (std::size_t i = 0; i < prev_size; ++i) {
        with_true[i] = std::tuple_cat(std::make_tuple(true), prev_combinations[i]);
    }

    // 填充追加false的数组
    for (std::size_t i = 0; i < prev_size; ++i) {
        with_false[i] = std::tuple_cat(std::make_tuple(false), prev_combinations[i]);
    }

    // 合并两个数组为最终结果
    std::array<ResultTuple, prev_size * 2> result;
    std::copy(with_true.begin(), with_true.end(), result.begin());
    std::copy(with_false.begin(), with_false.end(), result.begin() + prev_size);

    return result;
}

代码解释 #

1. 递归逻辑：

   • 对任意N>0，所有N长度布尔组合 = 所有N-1长度组合分别追加true + 所有N-1长度组合分别追加false。
   • N=0作为递归终止点，返回仅包含空元组的数组，是所有递归计算的基础。

2. C++17特性依赖：

   • constexpr函数：整个组合生成过程在编译时完成，运行时直接使用预计算结果。
   • std::array：编译时固定大小容器，适配2^N个固定数量的组合。
   • std::tuple_cat：编译时拼接元组，生成更长的布尔元组。
   • 类型推导：通过decltype自动推导元组和数组类型，避免手动书写冗长声明。

使用示例 #

#include <iostream>
#include <iomanip>

// 辅助函数：打印单个布尔元组
template <typename Tuple, std::size_t... Is>
void print_tuple(const Tuple& t, std::index_sequence<Is...>) {
    std::cout << "[";
    ((std::cout << std::boolalpha << std::get<Is>(t) << (Is != sizeof...(Is)-1 ? ", " : "")), ...);
    std::cout << "]\n";
}

template <typename Tuple>
void print_tuple(const Tuple& t) {
    print_tuple(t, std::make_index_sequence<std::tuple_size_v<Tuple>>{});
}

// 辅助函数：打印所有组合
template <typename Array>
void print_combinations(const Array& arr) {
    for (const auto& tuple : arr) {
        print_tuple(tuple);
    }
}

int main() {
    // 编译时生成N=3的所有布尔组合
    constexpr auto combos_3 = boolean_combinations<3>();
    
    // 打印结果（运行时）
    print_combinations(combos_3);
    
    // 编译时验证结果正确性
    static_assert(combos_3.size() == 8);
    static_assert(std::get<0>(combos_3) == std::make_tuple(true, true, true));
    static_assert(std::get<7>(combos_3) == std::make_tuple(false, false, false));
    
    return 0;
}

输出结果 #

运行代码后会输出：

[true, true, true]
[true, true, false]
[true, false, true]
[true, false, false]
[false, true, true]
[false, true, false]
[false, false, true]
[false, false, false]

内容的提问来源于stack exchange，提问作者ajl123