I am struggling with an implementation of the Cartesian product for
multiple indices with a given range 0,...,n-1.
The basic idea is to have a function:
cartesian_product<std::size_t range, std::size_t sets>()
with an output array that contains tuples that hold the different products
[(0,..,0), (0,...,1), (0,...,n-1),...., (n-1, ..., n-1)]
An simple example would be the following:
auto result = cartesian_product<3, 2>();
with the output type 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)]
My main problem is that my version of the Cartesian product is slow and creates a stack overflow if you choose to have more than 5 sets. I believe that my code has too many recursions and temporary variables.
My implementation (C++17) can be found here: 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;
}
Since I was also working on a solution I thought I post it aswell (although very similar to Artyer's answer). Same premise, we replace the tuple with an array and just iterate over the elements, incrementing them one by one.
Note that the power function is broken, so if you need power values <0 or non-integer types you have to fix it.
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;
}