Code It Yourself: Generate All the Combinations from Several Collections

A Cartesian product consists in applying a function to all the possible combinations of the elements of several collections.

For example, consider the three following collections:

auto const inputs1 = std::vector<int> {1, 2, 3};
auto const inputs2 = std::vector<std::string>{"up", "down"};
auto const inputs3 = std::vector<std::string>{"blue", "red"};

Then (2, up, blue) and (3, up, red) are two of the possible combinations of elements from those three collections.

In total, there are 3*2*2, that is 12 possible combinations.

If we apply the following function to each combination:

void displayCombination(int input1, std::string const& input2, std::string const& input3)
{
    std::cout << input1 << '-' << input2 << '-' << input3 << '\n';
}

Then we would expect an output looking like this:

1-up-blue
1-up-red
1-down-blue
1-down-red
2-up-blue
2-up-red
2-down-blue
2-down-red
3-up-blue
3-up-red
3-down-blue
3-down-red

Writing code that generates all those possible combinations is a very instructive exercise.

We’re going to see one way of achieving that in C++ but, since it’s instructive, I’d suggest that you give it a go first to benefit from the reflexion. You’ll have a chance to code it up right on this page, and in the next post we’ll see one possible solution.

The interface

We’d like to implement a Cartesian product that applies a function to each of the combinations of the elements coming from of an arbitrary number of collections.

A natural interface is to take the function as the first parameter, followed by a variadic pack of ranges:

template<typename Function, typename... Ranges>
void cartesian_product (Function function, Ranges const&... ranges)
{
    //...

There are as many parameters in function as the number of ranges in the variadic pack.

cartesian_product picks an element from each range of the pack and passes it to function.

Give it a try

If the requirement is clear, you can now try to implement it yourself!

Here is a playground with several test cases: a main one with a couple of ranges, and a few corner cases where one of the ranges is empty. In those last cases, we don’t expect the cartesian_product to generate any combination. Indeed, a combination has to take elements from all the input ranges.

Here is the playground:

Alternatively, you can use this Coliru link and keep your attempts for later reference.

In a couple of days I’ll share with you one possible way to implement cartesian_product. In the meantime, if you write expressive code that passes the above tests, I’d love to see it!

Please share it a Godbolt link in the comment section below.

Happy coding!

You will also like

Don't want to miss out ? Follow:   
Share this post!