I'm sure other people have already come up with similar ideas, but I wanted to share this cool trick.

Introduction

C++ has next_permutation which is very nice, but what about all the other combinatorics functions like Python has in the very nice itertools library. How should you go about writing a C++ brute force solution that uses things like combinations, Cartesian product/power, etc. Will you have to write the annoying (and quite large overhead) recursive backtracking? In this blog I show a light, efficient, and quite general way to do this type of thing using macros.

Cartesian Power

Let's start with the most simple example to introduce the idea. We want to enumerate $$$[0, a)^N$$$. To do this, we first set up an array int c[N] to hold the current element. Then, the critical part is do define a macro as follows: #define F(i) for (c[i]=0; c[i]<a; ++c[i]). This lets us loop any one of our indices. The full code to use this looks as follows (for $$$N=10, a=3$$$):

int c[10];
#define F(i) for (c[i]=0; c[i]<3; ++c[i])
F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)F(8)F(9){
    // Your code that operates on c[] here
}

(notice that the brackets are nice too ☺)

Now let me address some points about this. To start, one may be worried about the typing. This is a non-issue: even with $$$a=2$$$, we have $$$2^{30}>1e9$$$ which is fine. Next is questions of compile/run time. While $$$a$$$ can be completely set at run-time, $$$N$$$ doesn't seem as flexible. However, there are a couple of ways to do this. First, if your code is just doing a search, you can just treat c[] to be of length n (which is what I'll denote the run-time length), and ignore the rest of the elements. But if you don't want to repeat elements, or you have weird interaction with time complexity, there is another trick. We can rewrite our macro as #define F(i) for (c[i]=0; c[i]<(i<n ? a : 0); ++c[i]) to properly enumerate only the elements wanted at run-time.

Finally, you may say that this is stupid and that you can just do bitmask-type stuff (but using /a and %a instead of shifts). Initially I would have agreed with that, and was only intending to use this example pedagogically for more complex things. However, I was very surprised, because my way is actually much faster than that way (obviously except when $$$a$$$ is power of $$$2$$$). Even for $$$a=3$$$, where the compiler rather famously optimizes away the div and mod,