How to Create a N Way Cartesian Product of Type Lists in C++

How can I create a n way Cartesian product of type lists in C++?

With Boost.Mp11, this is a short one-liner (as always):

using result = mp_product<
    type_list,
    type_list_1, type_list_2, type_list_3>;

Demo.

How to create the Cartesian product of a type list?

Somehow my brain is fried: I think I'm using more code than is needed but, at least, it has the desired results (although I didn't fix the memory leak):

#include <iostream>
#include <typeinfo>
#include <cxxabi.h>

template<typename...> struct type_list {};

template<typename T1, typename T2> struct type_pair {};

template<typename T, typename... Rest>
  struct row
{
  typedef type_list<type_pair<T,Rest>...> type;
};

template <typename... T> struct concat;
template <typename... S, typename... T>
struct concat<type_list<S...>, type_list<T...>>
{
    typedef type_list<S..., T...> type;
};

template <typename... T>
struct expand
{
    typedef type_list<T...> type;
};
template <> struct expand<> { typedef type_list<> type; };
template <typename... T, typename... L>
struct expand<type_list<T...>, L...>
{
    typedef typename concat<typename expand<T...>::type, typename expand<L...>::type>::type type;
};

template<typename... T>
  struct cross_product
{
    typedef typename expand<type_list<typename row<T,T...>::type...>>::type type;

};

int main()
{
  int s;
  typedef cross_product<int, float, short>::type result;
  std::cout << abi::__cxa_demangle(typeid(result).name(), 0, 0, &s) << std::endl;

  return 0;
}

Cartesian product of std::tuple

One of the workarounds is to omit the function definition and directly use decltype to infer the return type:

template<typename T1, typename T2>
class CartesianProduct {
  template<typename T, typename... Ts>
  static auto innerHelper(T&&, std::tuple<Ts...>&&) 
  -> decltype(
       std::make_tuple(
         std::make_tuple(std::declval<T>(), std::declval<Ts>())...));

  template <typename... Ts, typename T>
  static auto outerHelper(std::tuple<Ts...>&&, T&&) 
  -> decltype(
       std::tuple_cat(innerHelper(std::declval<Ts>(), std::declval<T>())...));

 public:
  using type = decltype(outerHelper(std::declval<T1>(), std::declval<T2>()));
};

class Example {
  Example() = delete;
  Example(const Example&) = delete;
};

using T1 = std::tuple<Example>;
using T2 = std::tuple<int, double>;
static_assert(
  std::is_same_v<
    CartesianProduct_t<T1, T2>, 
    std::tuple<std::tuple<Example, int>, std::tuple<Example, double>>>);

Demo.

N-ary cartesian product of variadic templates

NOTE: A possible specialization for the thing I'm looking for would
be, but that is just a suggestion:

For the n-ary version, you only need to recurse the binary version since pack_product<a, b, c> is equivalent to pack_product<pack_product<a, b>, c>

// Cartesian product of packs: n-ary specialization
template <class Type1, class... Types1, class... Types2, class... Pack>
struct pack_product<pack<Type1, Types1...>, pack<Types2...>, Pack...> {
  using type = typename pack_product<typename pack_sum<
    pack<pack<Type1, Types2>...>,
    typename pack_product<pack<Types1...>, pack<Types2...>>::type
  >::type, Pack...>::type;
};

However, this will generate

{pack<pack<pack<signed char, float>, int>, pack<pack<signed char, float>, unsigned int>, ...}

In order to remove nested packs, partial specialization can be performed on binary/n-arg specialization

// Cartesian product of packs: binary specialization for nested packs
template <class... Types, class... Types1, class... Types2>
struct pack_product<pack<pack<Types...>, Types1...>, pack<Types2...>> {
  using type = typename pack_sum<
    pack<pack<Types..., Types2>...>,
    typename pack_product<pack<Types1...>, pack<Types2...>>::type
  >::type;
};

Demo

Doing cartesian product the functional way in C++17

Your compilation issues are because you are not capturing the needed variables in your lambdas, and you're missing some ;.

However, a simpler way to do a cartesian product is with 2 nested loops, like this:

for (int i : a)
  for (int j : b)
    cartesian.push_back(i * i + j * j);

---

If you want to use algorithms, then you can write:

for_each(begin(a), end(a), [&](int i) { 
  for_each(begin(b), end(b), [&](int j) { 
    cartesian.push_back(i * i + j * j); 
  });
});

although I find this harder to read, and doesn't really help much since for_each is an algorithm that happens to have an in-built language construct, similar to transform.

---

From c++20, ranges and views have been added, and so you can get considerably more creative:

namespace rs = std::ranges;
namespace rv = std::views;

auto product = [=](int i) 
{
   auto  op = [=](int j) { return i * i + j * j;};

   return b | rv::transform(op);
};
  
rs::copy(a | rv::transform(product) 
           | rv::join,
         std::back_inserter(cartesian));

Again, the original nested for loops are probably the best approach for a cartesian product, but this should give you a taste for the exciting possibilities.

Here's a demo.

Cartesian Product of an arbitrary number of objects

I consider this duplicate of question linked in comments, but since it was reopened and you struggle to adapt that question to your case, here is how.

First grab function by Eric Lippert from duplicate question as is (how it works is explained there):

public static class Extensions {
    public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
    {
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
        return sequences.Aggregate(
            emptyProduct,
            (accumulator, sequence) =>
                from accseq in accumulator
                from item in sequence
                select accseq.Concat(new[] { item })
        );
    }
}

Then flatten your input. Basically just attach corresponding label to each id:

var flatten = inputs.Select(c => c.Ids.Select(r => new Result {Label = c.Label, Id = r}));

Then run cartesian product and done:

// your expected result
var result = flatten.CartesianProduct().Select(r => r.ToList()).ToList();            

How can I calculate the cartesian product of n lists of different types?

Theoretically you can't do exactly what you want to do, but you can get pretty close to it. The reason why you cannot create such a function is because of static typing.

With tuples you can combine values of different types, but to ensure type-safety a tuple must be fixed-size and the type of every element must be known.

A list can contain a variable amount of elements, but because of this the type of every element must be the same. Otherwise you couldn't work with it in a static typed language.

In a dynamic typed language you could for example create a single function that takes a list of list (A) and another list (B). Then you add every element from B to every list inside of A and you are done. You also could do the same in a static typed language with two ideas:

1. You convert every element of the list to object first.
2. You create a Discriminated Union of every type first.

The first idea would mean you need a lot of down and up-casting, this is usually not what you want in a static-typed language. The second approach works but you must convert every single list to your DU type (you also need to create a DU), and later on you need to pattern match. Technically it is the same as 1. only in a more type-safe way.

Another approach and that is what I recommend is the usage of an Applicative. An applicative actually means you upgrade a function so every argument of a function can be an option, list and so on. So you first create an apply function like this:

let apply fs xs = [
    for f in fs do
    for x in xs do
        yield f x
]
let (<*>) = apply

once you have such a function you can write something like this:

[fun a b c d -> (a,b,c,d)]
    <*> [1..5]
    <*> ["a";"b"]
    <*> [(0,0);(1,1)]
    <*> [100;200]

This then returns a list containing:

[(1, "a", (0, 0), 100); (1, "a", (0, 0), 200); (1, "a", (1, 1), 100);
 (1, "a", (1, 1), 200); (1, "b", (0, 0), 100); (1, "b", (0, 0), 200);
 (1, "b", (1, 1), 100); (1, "b", (1, 1), 200); (2, "a", (0, 0), 100);
 (2, "a", (0, 0), 200); (2, "a", (1, 1), 100); (2, "a", (1, 1), 200);
 (2, "b", (0, 0), 100); (2, "b", (0, 0), 200); (2, "b", (1, 1), 100);
 (2, "b", (1, 1), 200); (3, "a", (0, 0), 100); (3, "a", (0, 0), 200);
 (3, "a", (1, 1), 100); (3, "a", (1, 1), 200); (3, "b", (0, 0), 100);
 (3, "b", (0, 0), 200); (3, "b", (1, 1), 100); (3, "b", (1, 1), 200);
 (4, "a", (0, 0), 100); (4, "a", (0, 0), 200); (4, "a", (1, 1), 100);
 (4, "a", (1, 1), 200); (4, "b", (0, 0), 100); (4, "b", (0, 0), 200);
 (4, "b", (1, 1), 100); (4, "b", (1, 1), 200); (5, "a", (0, 0), 100);
 (5, "a", (0, 0), 200); (5, "a", (1, 1), 100); (5, "a", (1, 1), 200);
 (5, "b", (0, 0), 100); (5, "b", (0, 0), 200); (5, "b", (1, 1), 100);
 (5, "b", (1, 1), 200)]

If you don't want to create the operator <*> you also could write:

[fun a b c d -> (a,b,c,d)]
    |> apply <| [1..5]
    |> apply <| ["a";"b"]
    |> apply <| [(0,0);(1,1)]
    |> apply <| [100;200]

but I usually discourage the usage of <|. I would prefer this instead:

let ap xs fs = [
    for f in fs do
    for x in xs do
        yield f x
]

[fun a b c d -> (a,b,c,d)]
    |> ap [1..5]
    |> ap ["a";"b"]
    |> ap [(0,0);(1,1)]
    |> ap [100;200]

The only thing you must create on-the-fly is the first-line. A function that maps four, five, six, ... arguments to a tuple.

If you want to know more about Applicatives and how it works exactly, I have written two blog-posts about this topic:

http://sidburn.github.io/blog/2016/04/13/applicative-list
http://sidburn.github.io/blog/2016/03/31/applicative-functors

Create cartesian product expansion of two variadic, non-type template parameter packs

You may do something like the following:

template <int... Is>
using u_list = std::integer_sequence<int, Is...>;

template <char... Cs>
using c_list = std::integer_sequence<char, Cs...>;

template<int, char> struct foo {};

template<class ...> struct bar {};

template <std::size_t I, typename T, template <typename, T...> class C, T ... Is>
constexpr T get(C<T, Is...> c)
{
    constexpr T values[] = {Is...};
    return values[I];
}

template <std::size_t I, typename T>
constexpr auto get_v = get<I>(T{});

template<int... Ints, char ... Chars, std::size_t ... Is>
auto cartesian_product(u_list<Ints...>, c_list<Chars...>, std::index_sequence<Is...>)
-> bar<foo<
        get_v<Is / sizeof...(Chars), u_list<Ints...> >,
        get_v<Is % sizeof...(Chars), c_list<Chars...> >
        >...
    >;

template<int... Ints, char ... Chars>
auto cartesian_product(u_list<Ints...> u, c_list<Chars...> c)
-> decltype(cartesian_product(u, c, std::make_index_sequence<sizeof...(Ints) * sizeof...(Chars)>()));

using int_vals = u_list<1, 5, 7>;
using char_vals = c_list<-3, 3>;

using result_t = decltype(cartesian_product(int_vals{}, char_vals{}));

Demo

Possible implementation of std part:

template <typename T, T ... Is> struct integer_sequence{};

template <std::size_t ... Is>
using index_sequence = integer_sequence<std::size_t, Is...>;

template <std::size_t N, std::size_t... Is>
struct make_index_sequence : make_index_sequence<N - 1, N - 1, Is...> {};

template <std::size_t... Is>
struct make_index_sequence<0u, Is...> : index_sequence<Is...> {};

And change in answer:

template <std::size_t I, typename T, template <typename, T...> class C, T ... Is>
constexpr T get(C<T, Is...> c)
{
    using array = T[];
    return array{Is...}[I];
}

template<int... Ints, char ... Chars, std::size_t ... Is>
auto cartesian_product(u_list<Ints...>, c_list<Chars...>, index_sequence<Is...>)
-> bar<foo<
        get<Is / sizeof...(Chars)>(u_list<Ints...>{}),
        get<Is % sizeof...(Chars)>(c_list<Chars...>{})
        >...
    >;

Demo C++11

---

Related Topics