Wsrtjtyk

I've got the following code that combines two vectors of arbitrary types into a combinatorial, i.e. std::vector<std::tuple<A, B>>.

template<class A, class B>

std::vector<std::tuple<A, B>> combine(const std::vector<A>& a, const std::vector<B>& b) {



    const auto combine_parts_ = (const A& x, const B& y) {

        auto result = std::tuple_cat(std::make_tuple(x), std::make_tuple(y));

        return result;

    };



    std::vector<std::tuple<A, B>> results;



    for (const auto& x : a) {

        for (const auto& y : b) {

            results.push_back(combine_parts_(x, y));

        }

    }



    return results;

}

However, I'm unclear how to extend that to an arbitrary number of types/vectors. I don't care about duplicate types; in fact there may be two or more sets of the same type involved. That's okay.

Some example use cases, for instance:

const auto combinations = combine(

    std::vector<int>({1,2,3})

    , std::vector<int>({1,2,3})

);

const auto combinations2 = combine(

    std::vector<int>({1,2,3})

    , std::vector<int>({1,2,3})

    , std::vector<bool>({true,false})

);

const auto combinations3 = combine(

    std::vector<int>({1,2,3})

    , std::vector<int>({1,2,3})

    , std::vector<bool>({true,false})

    , std::vector<char>({'a','b','c','d','e'})

);

Chiefly, what I want to do is avoid the ugly nested for loop. At the same time, I want to combine some unit testing combinatorial use cases in order to work with the resulting std::tuple<...> as the test case.

Note, I am not talking about permutations of a homogeneous set here. That's been a point of confusion from prior questions.

I think it might have something to do with templates, variadics, std::tuple_cat, somewhere along the way, but I don't know.

Thoughts? Suggestions?

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 cartesian_product_apply(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{};



    do {

        apply_impl(f, std::index_sequence_for<Ts...>(), it, std::tie(vs...));

    } while (increase(sizes, it));

}

And finally:

template <typename ... Ts>

std::vector<std::tuple<Ts...>> cartesian_product(const std::vector<Ts>&... vs)

{

    std::vector<std::tuple<Ts...>> res;



    cartesian_product_apply([&res](const auto&... args) { res.emplace_back(args...); },

                            vs...);

    return res;

}

With usage similar to:

std::vector<int> v1 = {1, 2, 3};

std::vector<std::string> v2 = {" A "," B "};

std::vector<int> v3 = {4, 5};



const auto res = cartesian_product(v1, v2, v3);

for (const auto& t : res) {

    // ...

}

Demo

Slightly adapted, and with warnings disabled:

struct CartesianProduct {



    template<typename... Tys>

    std::vector<std::tuple<Tys...>> operator()(const std::vector<Tys>&... vectors) {

        std::vector<std::tuple<Tys...>> results;

        apply([&results](const auto&... args) {

            results.emplace_back(args...); }, vectors...);

        return results;

    }



private:



    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 Cb, std::size_t... Is, std::size_t N, typename Tup>

    void __apply_impl(Cb&& cb, std::index_sequence<Is...>

        , const std::array<std::size_t, N>& it, const Tup& tup) {

        cb(std::get<Is>(tup)[it[Is]]...);

    }



    template <typename Cb, typename... Tys>

    void apply(Cb&& cb, const std::vector<Tys>&... vectors) {

        constexpr std::size_t N = sizeof...(Tys);

        std::array<std::size_t, N> sizes{ {vectors.size()...} };

#pragma warning (disable: 4834)

        // TODO: TBD: warning C4834: discarding return value of function with 'nodiscard' attribute...

        std::array<std::size_t, N> it{ {(vectors.size(), 0u)...} };

#pragma warning (default: 4834)



        do {

            __apply_impl(cb, std::index_sequence_for<Tys...>(), it, std::tie(vectors...));

        } while (__increase(sizes, it));

    }

};

Remembered to include tuple, vector, as well as array.

Simple to use:

CartesianProduct prod;

// ...

const auto product_ = prod(ints_, doubles_, bools_);

CHECK(std::tuple_size<decltype(product_ )::value_type>::value == 3);

Although not entirely positive what the warning is all about.