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 by hand. 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 : 1); ++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$$$). I did not do exhaustive benchmarks, but even for $$$a=3$$$, where the compiler rather famously optimizes away the div and mod, my way seemed to be 3-5 times faster (perhaps because multiply still exists for $$$/3$$$).

Cartesian Product

A slightly more complicated variant might be to do $$$[0, a_0) \times [0, a_1] \times ... \times [0, a_{N-1}]$$$. This only requires a small change from above, where instead of having c[i]<a in your macro, you generalize to c[i]<a[i]. An example code might look like:

int c[10];
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
#define F(i) for (c[i]=0; c[i]<a[i]; ++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
}

A very nice thing about this operation is that the run/compile time issue with $$$a$$$ disappears. You can just set all the a[i]=1 for $$$i\geq n$$$.

More general elements

What if I want to do some range $$$[a, b)$$$ instead of $$$[0, a)$$$? Well, just do $$$[0, b-a)$$$ and add $$$a$$$ before using. Perhaps more useful, what if I want some arbitrary sequence(s) of elements. That is also easy: let your a be the size(s) of your sequences, and use elements from c[] as indices into you sequence(s). Here is some code (for cartesian product) for that:

vector<int> seq[10];
// seq is filled in by your code

int c[10];
#define F(i) for (c[i]=0; c[i]<seq[i].size(); ++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 seq[i][c[i]] here
}

The same trick applies for also the operations below, so I will only focus on the reduced case of $$$[0, a)$$$.

Combinations

In this operation we are enumerating all $$$N$$$ element combinations from $$$[0, a)$$$. The trick here, is to keep forcing the next element to be greater than the previous, so that we ensure the elements are distinct, and only ever in one order. The macro looks as follows: #define F(i) for (c[i]=(i ? c[i-1]+1 : 0); c[i]<a; ++c[i]).

One note is that if you are going to try and do the run-time cutoff trick from above, you also need to change the initialization of c[i]$ part because then the inner for-loops might never run for some elements.

Combinations with Replacement

For this operation the code is nearly the same, except we want to allow repeats: #define F(i) for (c[i]=(i ? c[i-1] : 0); c[i]<a; ++c[i]).

Other operations

I am not really sure how to do other operations, but if you smart people have any ideas or other approaches, please leave it in the comments. (This is not strictly true, I know for permutations one can do the combinations thing and then use next_permutation(), but that is very clunky). Some that would be useful are permutations and partitions.