создать кортеж n-го элемента в декартовом произведении входных векторов

Question

У меня есть функция python, которая возвращает n-й элемент в декартовом произведении ряда входных массивов

def prod(n, arrs):
    out = []

    for i,arr in enumerate(arrs):
        denom = numpy.prod([ len(p) for p in arrs[i+1:] ], dtype=int)
        idx = n // denom % len(arr)
        out.append( arr[idx] )

    return out

Это прекрасно работает:

a = [ 1000, 1100, 1200, 1300, 1400 ]
b = [ 1.0, 1.5, 2.0, 2.5, 3.0, 3.5 ]
c = [ -2, -1, 0, 1, 2 ]

for n in range(20, 30):
    i = prod(n, [a, b, c])
    print(n, i)

[1000, 3.0, -2]
[1000, 3.0, -1]
[1000, 3.0, 0]
[1000, 3.0, 1]
[1000, 3.0, 2]
[1000, 3.5, -2]
[1000, 3.5, -1]
[1000, 3.5, 0]
[1000, 3.5, 1]
[1000, 3.5, 2]

Теперь я хотел бы перевести это на C ++ (макс. Стандарт C ++ - 17)

template<typename... Ts>
auto prod(std::size_t n, const std::vector<Ts>&... vs) 
    -> std::tuple<const std::decay_t<typename std::vector<Ts>::value_type>&...>
{
    // template magic here
}

Может кто-нибудь помочь мне с шаблоном magi c, необходимым для построения кортежа с использованием приведенная выше формула?

Answer 1

Во-первых, давайте просто для простоты автоматически выведем тип возвращаемого значения функции.

Далее, индексные последовательности аккуратны. С ними это можно сделать.

С C ++ 20 мы могли бы получить индексы из последовательности в лямбде. Перед этим нам нужна дополнительная функция.

Наконец, мы должны начать создавать индексы с конца, либо хранить индексы, а затем использовать их в обратном порядке или инвертировать полученный кортеж.

template <class T, std::size_t... Ns>
static auto prod_impl(std::size_t n, T tuple, std::index_sequence<Ns...>) {
    auto f = [&](auto N){ auto r = n % N; n /= N; return r; };
    auto x = std::forward_as_tuple(std::get<(sizeof...(Ns)) - Ns - 1>(tuple)[f(std::get<(sizeof...(Ns)) - Ns - 1>(tuple).size())]...);
    return std::forward_as_tuple(std::get<(sizeof...(Ns)) - Ns - 1>(x)...);
}

template<class... Ts>
auto prod(std::size_t n, const std::vector<Ts>&... vs) {
    return prod_impl(n, std::forward_as_tuple(vs...), std::make_index_sequence<sizeof...(vs)>());
}

Более простая альтернатива для внутренней функции с использованием массива индексов:

template <class T, std::size_t... Ns>
static auto prod_impl(std::size_t n, T tuple, std::index_sequence<Ns...>) {
    auto f = [&](auto N){ auto r = n % N; n /= N; return r; };
    std::size_t Is[] = { f(std::get<sizeof...(Ns) - Ns - 1>(tuple).size())... , 0};
    return std::forward_as_tuple(std::get<Ns>(tuple)[sizeof...(Ns) - Ns - 1]...);
}

Answer 2

В других ответах уже упоминался трюк с индексами. Вот моя попытка, преобразованная как можно напрямую из вашего python кода:

template <typename T, std::size_t... I>
auto prod_impl(std::size_t n, T tuple, std::index_sequence<I...>) {
    std::array sizes{ std::size(std::get<I>(tuple))... };
    auto enumerator = [&sizes,n](std::size_t i, auto&& arr) -> decltype(auto) {
        auto denom = std::accumulate(std::begin(sizes) + i + 1, std::end(sizes), 1, std::multiplies<>{});
        auto idx = (n / denom) % std::size(arr);
        return arr[idx];
    };

    return std::forward_as_tuple(enumerator(I, std::get<I>(tuple))...);
}

template<typename... Ts, typename Is = std::index_sequence_for<Ts...>>
auto prod(std::size_t n, const std::vector<Ts>&... vs) {
    return prod_impl(n, std::forward_as_tuple(vs...), Is{});
}

(пример в реальном времени: http://coliru.stacked-crooked.com/a/a8b975c29d429054)

Answer 3

Мы можем использовать "трюк с индексами" , чтобы получить индексы, связанные с различными векторами.

Это дает нам следующее решение C ++ 14:

#include <tuple>
#include <vector>
#include <cstdlib>

using std::array;
using std::size_t;

template <size_t NDim>
constexpr array<size_t, NDim> delinearize_coordinates(
    size_t n, array<size_t, NDim> dimensions) 
{
    // This might be optimizable into something nicer, maybe even a one-liner
    array<size_t, NDim> result{};
    for(size_t i = 0; i < NDim; i++) {
        result[NDim-1-i] = n % dimensions[NDim-1-i];
        n = n / dimensions[NDim-1-i];
    };
    return result;
}

template<size_t... Is, typename... Ts>
auto prod_inner(
    std::index_sequence<Is...>,
    size_t n, 
    const std::vector<Ts>&... vs) 
    -> std::tuple<const std::decay_t<typename std::vector<Ts>::value_type>&...>
{
    auto vs_as_tuple = std::make_tuple( vs ... );
    auto coordinates = delinearize_coordinates<sizeof...(Ts)>(n, { vs.size()... });
    return { std::get<Is>(vs_as_tuple)[coordinates[Is]] ... };
}

template<typename... Ts>
auto prod(size_t n, const std::vector<Ts>&... vs) 
    -> std::tuple<const std::decay_t<typename std::vector<Ts>::value_type>&...>
{
    return prod_inner(std::make_index_sequence<sizeof...(Ts)>{}, n,
        std::forward<const std::vector<Ts>&>(vs)...);
}

Примечания:

• В отличие от вашего кода, я выделил функцию который переводит одно число в последовательность координат.
• Я думаю, что вы можете получить это до C ++ 11, если вы предоставите свой собственный make_index_sequence.