c++ - 编译时多个集合的笛卡尔积

Question

我正在努力实现笛卡尔积 给定范围的多个索引0,...,n-1 .

基本思想是有一个函数:

cartesian_product<std::size_t range, std::size_t sets>()

输出数组包含保存不同产品的元组

[(0,..,0), (0,...,1), (0,...,n-1),...., (n-1, ..., n-1)]

一个简单的例子如下:

auto result = cartesian_product<3, 2>();

输出类型为std::array<std::tuple<int, int>, (3^2)> :

[(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)]

我的主要问题是我的笛卡尔积版本很慢，如果您选择超过 5 个集合，则会导致堆栈溢出。我认为我的代码有太多递归和临时变量。

我的实现(C++17)可以在这里找到:cartesian_product

#include <stdio.h>
#include <iostream>

#include <tuple>


template<typename T, std::size_t ...is>
constexpr auto flatten_tuple_i(T tuple, std::index_sequence<is...>) {

    return std::tuple_cat(std::get<is>(tuple)...);

}

template<typename T>
constexpr auto flatten_tuple(T tuple) {
    return flatten_tuple_i(tuple, std::make_index_sequence<std::tuple_size<T>::value>{});
}

template<std::size_t depth, typename T>
constexpr auto recursive_flatten_tuple(T tuple){

    if constexpr(depth <= 1){
        return tuple;
    }else{
        return recursive_flatten_tuple<depth-1>(flatten_tuple(tuple));
    }
}

template<std::size_t depth, typename T, std::size_t ...is>
constexpr auto wdh(T&& tuple, std::index_sequence<is...>){

    if constexpr (depth == 0) {
        return tuple;
    }else{
        //return (wdh<depth-1>(std::tuple_cat(tuple, std::make_tuple(is)),std::make_index_sequence<sizeof...(is)>{})...);
        return std::make_tuple(wdh<depth-1>(std::tuple_cat(tuple, std::make_tuple(is)), std::make_index_sequence<sizeof...(is)>{})...);
    }
}

template<std::size_t sets, typename T, std::size_t ...is>
constexpr auto to_array(T tuple, std::index_sequence<is...>){

    if constexpr (sets == 0){
        auto t = (std::make_tuple(std::get<is>(tuple)),...);
        std::array<decltype(t), sizeof...(is)> arr = {std::make_tuple(std::get<is>(tuple))...};
        //decltype(arr)::foo = 1;
        return arr;
    }else{
        auto t = ((std::get<is>(tuple)),...);
        std::array<decltype(t), sizeof...(is)> arr = {std::get<is>(tuple)...};
        return arr;
    }
}

template<std::size_t sets, std::size_t ...is>
constexpr auto ct_i(std::index_sequence<is...>){

    if constexpr (sets == 0){

        auto u = std::tuple_cat(wdh<sets>(std::make_tuple(is), std::make_index_sequence<sizeof...(is)>{})...);
        auto arr = to_array<sets>(u, std::make_index_sequence<std::tuple_size<decltype(u)>::value>{});

        return arr;

    }else {

        auto u = std::tuple_cat(wdh<sets>(std::make_tuple(is), std::make_index_sequence<sizeof...(is)>{})...);

        auto r = recursive_flatten_tuple<sets>(u);

        auto d = to_array<sets>(r, std::make_index_sequence<std::tuple_size<decltype(r)>::value>{});


        return d;
    }

}

template<std::size_t range, std::size_t sets>
constexpr auto cartesian_product(){

    static_assert( (range > 0), "lowest input must be cartesian<1,1>" );
    static_assert( (sets > 0), "lowest input must be cartesian<1,1>" );
    return ct_i<sets-1>(std::make_index_sequence<range>{});
}


int main()
{
    constexpr auto crt = cartesian_product<3, 2>();

    for(auto&& ele : crt){

        std::cout << std::get<0>(ele) << " " << std::get<1>(ele) << std::endl;

    }

    return 0;
}

Answer 1

由于我也在研究一个解决方案，所以我想我也发布了它(尽管与 Artyer 的答案非常相似)。同样的前提，我们用数组替换元组，然后迭代元素，将它们一一递增。

请注意，power 函数已损坏，因此如果您需要功率值 <0 或非整数类型，则必须修复它。

template <typename It, typename T>
constexpr void setAll(It begin, It end, T value)
{
    for (; begin != end; ++begin)
        *begin = value;
}

template <typename T, std::size_t I>
constexpr void increment(std::array<T, I>& counter, T max)
{
    for (auto idx = I; idx > 0;)
    {
        --idx;
        if (++counter[idx] >= max)
        {
            setAll(counter.begin() + idx, counter.end(), 0); // because std::fill is not constexpr yet          
        }
        else
        {
            break;
        }
    }
}

// std::pow is not constexpr
constexpr auto power = [](auto base, auto power)
{
    auto result = base;
    while (--power)
        result *= base;
    return result;
};

template<std::size_t range, std::size_t sets>
constexpr auto cartesian_product()
{
    std::array<std::array<int, sets>, power(range, sets)> products{};
    std::array<int, sets> currentSet{};

    for (auto& product : products)
    {
        product = currentSet;
        increment(currentSet, static_cast<int>(range));
    }

    return products;
}

int main()
{
    constexpr auto crt = cartesian_product<5, 3>();

    for (auto&& ele : crt) 
    {
        for (auto val : ele)
            std::cout << val << " ";
        std::cout << "\n";
    }

    return 0;
}

Example