Декартово произведение для нескольких множеств во время компиляции - PullRequest
Новая
       19

Декартово произведение для нескольких множеств во время компиляции

3 голосов
/ 07 марта 2020

Я борюсь с реализацией декартова произведения для нескольких индексов с заданным диапазоном 0,...,n-1.

Основная идея c состоит в том, чтобы иметь функцию:

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;
}

Ответы [ 5 ]

2 голосов
/ 08 марта 2020

С 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, что делает чтение более приятным (сверху вниз, а не снизу вверх).

Объяснение того, что происходит, на примере OP cartesian_product<3, 2>:

  • 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 s интегральных констант и превращает их в std::array из tuple s.

Немного другой подход, использующий только одну вспомогательную функцию: 

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)...);
                })...
            };
        });
}

Этот подход сложнее для чтения, но это тот же алгоритм.

2 голосов
/ 07 марта 2020

Поскольку я также работал над решением, я решил опубликовать его также (хотя и очень похоже на ответ Артье). То же самое, мы заменяем кортеж массивом и просто перебираем элементы, увеличивая их один за другим.

Обратите внимание, что функция power не работает, поэтому, если вам нужны значения мощности <0 или нецелые типы, вы должны исправить это. </p> 

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;
}

Пример

1 голос
/ 08 марта 2020

Если вы хотите это во время компиляции, вы должны использовать только оценки времени компиляции для структур данных времени компиляции. Как указал выше @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 s. Если у вас есть такие, преобразование их в значения времени выполнения тривиально. Обратите внимание, что cartesian_product даже не обязательно является функцией, так как весь набор данных оценивается во время компиляции, это может быть шаблонное значение.

1 голос
/ 07 марта 2020

Я попробовал это просто для удовольствия, и у меня закончилась почти та же идея, что и у @Timo, просто с другим форматом / стилем. 

#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]

Примерно так же, как вы бы сделали это вручную.

Пример

1 голос
/ 07 марта 2020

Вы можете сделать это без рекурсии легко. Обратите внимание, что каждый кортеж представляет собой цифры чисел от 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;
}

Вот тестовая ссылка: https://www.onlinegdb.com/By_X9wbrI

Обратите внимание, что (empty_set)^0 определяется как набор, содержащий здесь пустой набор, но это можно изменить, сделав ipow(0, 0) == 0 вместо 1

...