How to Create the Cartesian Product of a Type List

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

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.

Cartesian product of list of templates and list of types to instantiate them with

As in my answer on he linked question, with Boost.Mp11, this is a short one-liner (as always):

using templates = mp_list<mp_quote<std::vector>, mp_quote<std::set>>;
using types = mp_list<int, double>;

using result = mp_product<
    mp_invoke_q,
    templates, types>;

static_assert(std::same_as<
    result,
    mp_list<std::vector<int>,
            std::vector<double>,
            std::set<int>,
            std::set<double>
            >>);

Demo.

Note that you need templates as mp_list<mp_quote<C1>, mp_quote<C2>> instead of template_list<C1, C2>, since metaprogramming is lot easier if everything is a type. But that's not a huge burden.

How to create a data structure similar to the cartesian product of three lists of different types?

I think this is what you want. Note that it is sometimes cleaner not to use streams.

public static void main(String[] args) throws Exception {
    List<String> strings = Collections.emptyList();
    List<Integer> ints = Arrays.asList(1, 2, 3);

    if (strings == null || strings.isEmpty()) {
        strings = Collections.singletonList(null);
    }

    if (ints == null || ints.isEmpty()) {
        ints = Collections.singletonList(null);
    }

    for (String str : strings) {
        for (Integer integer : ints) {
            // In your code doubles comes from a property of integer.
            List<Double> doubles = integer == null ? Collections.emptyList() : Arrays.asList(1.0d, 2.0d, 3.0d);

            if (doubles == null || doubles.isEmpty()) {
                doubles = Collections.singletonList(null);
            }

            for (Double doubler : doubles) {
                // Create your object here.
                System.out.format(Locale.US, "    str = %s, int = %d, double = %f %n", str, integer, doubler);
            }
        }
    }
}

Output follows:

str = null, int = 1, double = 1.000000 
str = null, int = 1, double = 2.000000
str = null, int = 1, double = 3.000000
str = null, int = 2, double = 1.000000
str = null, int = 2, double = 2.000000 
str = null, int = 2, double = 3.000000
str = null, int = 3, double = 1.000000
str = null, int = 3, double = 2.000000
str = null, int = 3, double = 3.000000

Cartesian product between list inside a list

This is generic for element type but specific for collection type, i.e. List.

def cProd[T](in: List[List[T]]): List[List[T]] =
  in.foldRight(List(List.empty[T])) {
    for {word <- _ ; sentence <- _} yield word :: sentence
  }

It can be made more general for collection type but you'd likely loose some List optimizations.

Get the cartesian product of a series of lists?

itertools.product

Available from Python 2.6.

import itertools

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]
for element in itertools.product(*somelists):
    print(element)

Which is the same as,

for element in itertools.product([1, 2, 3], ['a', 'b'], [4, 5]):
    print(element)

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

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.

---

Related Topics