Macro Combinatorics

Revision en2, by akifpatel, 2020-06-16 21:18:24

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.

Tags #combinatorics, #brute force, #implementation, #c++

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English akifpatel 2020-06-28 08:52:25 0 (published)
en5 English akifpatel 2020-06-28 08:51:37 2675 Tiny change: 'ents from $c[]$ as indice' -> 'ents from `c[]` as indice'
en4 English akifpatel 2020-06-16 21:51:17 1272
en3 English akifpatel 2020-06-16 21:26:18 449
en2 English akifpatel 2020-06-16 21:18:24 174
en1 English akifpatel 2020-06-16 18:17:35 622 Initial revision (saved to drafts)