我正在努力实现笛卡尔积的给定range 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;
}
0为基础的从range ** sets到range的数字的数字，因此您可以增加一个计数器（或应用于std::index_sequence）并一个接一个地计算每个值。[这里是一个实现（返回std::array的std::array，与std::tuple的工作原理基本相同，您可以在get<N>上使用tuple_size，tuple_element<N>和std::array您真的希望可以将它们转换为std::tuple s）：
#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;
}