CODEWITHSUNDEEP
c++combinatoricscartesian-product
mwpowellhtx
mwpowellhtx

Reputation: 351

How to generate tupled combinations of arbitrary number of vectors

This question was kind of asked before, but I'm not sure a satisfactory response was really offered. For me, I'm not interested in landing in a std::vector of std::string, per se, but rather a std::tuple.

For instance, if I've got std::vector<A>, std::vector<B>, and std::vector<C>, then I expect perhaps std::vector<std::tuple<A, B, C>>. Or, even std::set<std::tuple<A, B, C>>, if that was more appropriate.

Now, I could encode nested for loops, however, I'd like to do this via functions, template functions if possible, then I suppose variadic would be necessary to accomplish the task.

There are no guarantees that A, B, or C have anything to do with each other, much less conversion to std::string, as were proposed in a couple of the responses.

I want to say there could be a variadic solution to that, but I'm not exactly sure how to compose the std::vector<T> or std::vector<T>::value_type definitions.

Upvotes: 2

Views: 102

Answers (1)

Jarod42
Jarod42

Reputation: 217448

If you want to compute the Cartesian product of heterogeneous vectors, you may do something like:

template <std::size_t N>
bool increase(const std::array<std::size_t, N>& sizes, std::array<std::size_t, N>& it)
{
    for (std::size_t i = 0; i != N; ++i) {
        const std::size_t index = N - 1 - i;
        ++it[index];
        if (it[index] >= sizes[index]) {
            it[index] = 0;
        } else {
            return true;
        }
    }
    return false;
}

template <typename F, std::size_t ... Is, std::size_t N, typename Tuple>
void apply_impl(F&& f,
                std::index_sequence<Is...>,
                const std::array<std::size_t, N>& it,
                const Tuple& tuple)
{
    f(std::get<Is>(tuple)[it[Is]]...);
}

template <typename F, typename ... Ts>
void iterate(F&& f, const std::vector<Ts>&... vs)
{
    constexpr std::size_t N = sizeof...(Ts);
    std::array<std::size_t, N> sizes{{vs.size()...}};
    std::array<std::size_t, N> it{{(vs.size(), 0u)...}};

    do {
        apply_impl(f, std::index_sequence_for<Ts...>(), it, std::tie(vs...));
    } while (increase(sizes, it));
}

Demo

Upvotes: 3

Related Questions