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

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

您无需递归即可轻松完成此操作。请注意，每个元组都是基数 range 中从 0 到 range ** sets 的数字的数字，因此您可以递增计数器（或应用于 std::index_sequence）并计算每个值一个接一个。

这是一个实现（returns std::array of std::arrays，它的工作原理与 std::tuples 基本相同，你可以 get<N>， tuple_size 和 tuple_element<N> 在 std::array 上，但如果你真的想要，你可以将它们转换为 std::tuples):

#include <cstddef>
#include <array>

namespace detail {
    constexpr std::size_t ipow(std::size_t base, std::size_t exponent) noexcept {
        std::size_t p = 1;
        while (exponent) {
            if (exponent % 2 != 0) {
                p *= base;
            }
            exponent /= 2;
            base *= base;
        }
        return p;
    }
}

template<std::size_t range, std::size_t sets>
constexpr std::array<std::array<std::size_t, sets>, detail::ipow(range, sets)>
cartesian_product() noexcept {
    constexpr std::size_t size = detail::ipow(range, sets);
    std::array<std::array<std::size_t, sets>, size> result{};
    for (std::size_t i = 0; i < size; ++i) {
        std::size_t place = size;
        for (std::size_t j = 0; j < sets; ++j) {
            place /= range;
            result[i][j] = (i / place) % range;
        }
    }
    return result;
}

这是一个测试link：https://www.onlinegdb.com/By_X9wbrI

请注意，(empty_set)^0 在这里被定义为一个包含空集的集合，但可以通过 ipow(0, 0) == 0 而不是 1

来更改

Answer 2

因为我也在研究一个解决方案，所以我想我也 post 它（尽管与 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

Answer 3

我只是为了好玩而尝试，结果我得到了与@Timo 几乎相同的想法，只是 format/style。

#include <iostream>
#include <array>
using namespace std;


template<size_t range, size_t sets>
constexpr auto cartesian_product() {
    // how many elements = range^sets
    constexpr auto size = []() {
        size_t x = range;
        size_t n = sets;
        while(--n != 0) x *= range;
        return x;
    }();

    auto products = array<array<size_t, sets>, size>();
    auto counter = array<size_t, sets>{}; // array of zeroes

    for (auto &product : products) {
        product = counter;

        // counter increment and wrapping/carry over
        counter.back()++;
        for (size_t i = counter.size()-1; i != 0; i--) {
            if (counter[i] == range) {
                counter[i] = 0;
                counter[i-1]++;
            }
            else break;
        }
    }
    return products;
}


int main() {
    auto prods = cartesian_product<3, 6>();
}

我基本上有一个手动递增的计数器数组，如下所示：

// given cartesian_product<3, 4>
[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 2]
[0, 0, 1, 0] // carry over
...
...
[2, 2, 2, 2]

几乎就是您手工完成的方式。

Example

Answer 4

对于 Boost.Mp11，这是...好吧，它不是单线的，但还算不错：

template <typename... Lists>
using list_product = mp_product<mp_list, Lists...>;

template <typename... Ts>
constexpr auto list_to_tuple(mp_list<Ts...>) {
    return std::make_tuple(int(Ts::value)...);
}

template <typename... Ls>
constexpr auto list_to_array(mp_list<Ls...>) {
    return std::array{list_to_tuple(Ls{})...};
}

template <size_t R, size_t N>
constexpr auto cartesian_product()
{
    using L = mp_repeat_c<mp_list<mp_iota_c<R>>, N>; 
    return list_to_array(mp_apply<list_product, L>{});
}

使用 C++20，您可以在 cartesian_product 中将两个辅助函数模板声明为 lambda，这样可以更好地阅读（从上到下而不是从下到上）。

根据 cartesian_product<3, 2> 的 OP 示例解释发生了什么：

mp_iota_c<R> 给我们列表 [0, 1, 2] （但作为整数常量类型）
mp_repeat_c<mp_list<mp_iota_c<R>>, N> 给我们 [[0, 1, 2], [0, 1, 2]]。我们只是重复列表，但我们想要一个列表列表（因此中间有额外的 mp_list）。
mp_apply<list_product, L> 执行 mp_product，这是您传入的所有列表的笛卡尔积...将结果粘贴在 mp_list 中。这给你 [[0, 0], [0, 1], [0, 2], ..., [2, 2]]，但作为整数常数 mp_list 的 mp_list。
此时困难的部分已经结束，我们只需要将结果转换回元组数组即可。 list_to_tuple 接受整数常数的 mp_list 并将其转换为具有正确值的 tuple<int...>。 list_to_array 将 mp_list 的 mp_list 整数常数转换为 std::array 的 tuple。

仅使用单个辅助函数的略有不同的方法：

template <template <typename...> class L,
    typename... Ts, typename F>
constexpr auto unpack(L<Ts...>, F f) {
    return f(Ts{}...);
}

template <size_t R, size_t N>
constexpr auto cartesian_product()
{
    using P = mp_apply_q<
        mp_bind_front<mp_product_q, mp_quote<mp_list>>,
        mp_repeat_c<mp_list<mp_iota_c<R>>, N>>;

    return unpack(P{},
        [](auto... lists){
            return std::array{
                unpack(lists, [](auto... values){
                    return std::make_tuple(int(values)...);
                })...
            };
        });
}

尽管这种方法更难阅读，但它是相同的算法。

Answer 5

如果你想在编译时使用它，你应该只对编译时数据结构使用编译时评估。正如@Barry 上面指出的那样，使用 Boost.Mp11 极大地促进了它。当然你可以自己用纯C++17重新实现相关的基础函数：

#include <iostream>

template<class T> struct Box {
        using type = T;
};


template<class... Types> struct List {};


template<class Car, class Cdr> struct Cons;
template<class Car, class Cdr> using ConsT = typename Cons<Car, Cdr>::type;

template<class Car, class... Cdr> struct Cons<Car, List<Cdr...>>: Box<List<Car, Cdr...>> {};


using Nil = List<>;


template<std::size_t i, class L> struct Nth;
template<std::size_t i, class L> using NthT = typename Nth<i, L>::type;

template<std::size_t i, class... Ts> struct Nth<i, List<Ts...>>: std::tuple_element<i, std::tuple<Ts...>> {};


template<class L> struct Head;
template<class L> using HeadT = typename Head<L>::type;

template<class Car, class... Cdr> struct Head<List<Car, Cdr...>>: Box<Car> {};


template<class L> struct Tail;
template<class L> using TailT = typename Tail<L>::type;

template<class Car, class... Cdr> struct Tail<List<Car, Cdr...>>: Box<List<Cdr...>> {};


template<class... Lists> struct Concat;
template<class... Lists> using ConcatT = typename Concat<Lists...>::type;

template<class T, class... Rest> struct Concat<T, Rest...>: Cons<T, ConcatT<Rest...>> {};

template<class Head, class... Tail, class... Rest> struct Concat<List<Head, Tail...>, Rest...>: Cons<Head, ConcatT<List<Tail...>, Rest...>> {};

template<class... Rest> struct Concat<Nil, Rest...>: Concat<Rest...> {};

template<> struct Concat<>: Box<Nil> {};


template<class T, class Subspace> struct Prepend;
template<class T, class Subspace> using PrependT = typename Prepend<T, Subspace>::type;

template<class T, class... Points> struct Prepend<T, List<Points...>>: Box<List<ConsT<T, Points>...>> {};

template<class T> struct Prepend<T, Nil>: Box<List<List<T>>> {};


template<class Range, class Subspace> struct Product;
template<class Range, class Subspace> using ProductT = typename Product<Range, Subspace>::type;

template<class Range, class Subspace> struct Product: Concat<PrependT<HeadT<Range>, Subspace>, ProductT<TailT<Range>, Subspace>> {};

template<class Subspace> struct Product<Nil, Subspace>: Box<Nil> {};


template<std::size_t i> using IntValue = std::integral_constant<std::size_t, i>;


template<class Seq> struct IntegerSequence;
template<class Seq> using IntegerSequenceT = typename IntegerSequence<Seq>::type;

template<std::size_t... is> struct IntegerSequence<std::index_sequence<is...>>: Box<List<IntValue<is>...>> {};


template<std::size_t n> using Range = IntegerSequenceT<std::make_index_sequence<n>>;


template<std::size_t dimensions, std::size_t range> struct CartesianCube;
template<std::size_t dimensions, std::size_t range> using CartesianCubeT = typename CartesianCube<dimensions, range>::type;

template<std::size_t dimensions, std::size_t range> struct CartesianCube: Product<Range<range>, CartesianCubeT<dimensions - 1, range>> {};

template<std::size_t range> struct CartesianCube<0, range>: Box<Nil> {};


template<std::size_t i> std::ostream &operator<<(std::ostream &s, IntValue<i>) {
        return s << '<' << i << '>';
}

template<class... Ts> std::ostream &operator<<(std::ostream &s, List<Ts...>);

namespace detail_ {

template<class L, std::size_t... is> std::ostream &printList(std::ostream &s, L, std::index_sequence<is...>) {
        return ((s << (is == 0? "" : ", ") << NthT<is, L>{}), ...), s;
}

}

template<class... Ts> std::ostream &operator<<(std::ostream &s, List<Ts...>) {
        return detail_::printList(s << "List{", List<Ts...>{}, std::index_sequence_for<Ts...>{}) << '}';
}

int main() {
        std::cout << CartesianCubeT<2, 3>{} << '\n';
}

注意这里的CartesianCubeT实际上是List个List个integral_constant个。一旦有了这些，将它们转换成运行时间值就很简单了。请注意 cartesian_product 甚至不必是函数，因为整个数据集是在编译时评估的，它可以是模板值。

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

Cartesian product for multiple sets at compile time

c++

templates

cartesian-product

c++17