Macro Combinatorics

Правка en3, от akifpatel, 2020-06-16 21:26:18

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
}
Теги #combinatorics, #brute force, #implementation, #c++

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский akifpatel 2020-06-28 08:52:25 0 (published)
en5 Английский akifpatel 2020-06-28 08:51:37 2675 Tiny change: 'ents from $c[]$ as indice' -> 'ents from `c[]` as indice'
en4 Английский akifpatel 2020-06-16 21:51:17 1272
en3 Английский akifpatel 2020-06-16 21:26:18 449
en2 Английский akifpatel 2020-06-16 21:18:24 174
en1 Английский akifpatel 2020-06-16 18:17:35 622 Initial revision (saved to drafts)