create tuple of nth element in the cartesian product of input vectors

Question

I have a python function which returns the nth-element in the cartesian product of a number of input arrays

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

This works great:

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]

Now I would like to translate this to C++ (max standard 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
}

Can someone help me with the template magic required to construct the tuple using the above formula?

Wow! Easy! For an explanation on why this works so well, check out this link: http://phrogz.net/lazy-cartesian-product — Abe Hoffman, Nov 29 '22 at 14:33

Deduplicator · Answer 1 · 2020-02-17T23:55:52.790

First, let's just auto-deduce the function's return type for simplicity.

Next, index-sequences are neat. With them, it can be done.

With C++20, we could get the indices from the sequence in a lambda. Before that, we need an extra function.

Finally, we have to start creating the indices from the end, either storing the indices and then using them in reverse order or reversing the resulting tuple.

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

Simpler alternative for the inner function using an array of indices:

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

einpoklum · Answer 2 · 2020-02-17T23:36:10.850

We can use the "indices trick" to get us indices associated with the different vectors.

This gets us the following C++14 solution:

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

Notes:

Unlike in your code, I've factored-out the function which translates a single number into a sequence of coordinates.
I think you can get this down to C++11 if you provide your own make_index_sequence.

N. Shead · Accepted Answer · 2020-02-17T23:53:59.063

The other answers have already mentioned the indices trick. Here is my attempt at it, converted as directly as possible from your python code:

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

(Live example: http://coliru.stacked-crooked.com/a/a8b975c29d429054)

create tuple of nth element in the cartesian product of input vectors

3 Answers3