Tag Archives: C++

Enumeration of Antimatroids, part IV

I promise to finish this topic with this post! (part 1, part 2, part 3)

We ended with a rather efficient (but still double exponential) code that gave us hope to extend the sequence a little bit further. So, what can we improve? Constant, a little, by efficient parallelisation.

Enumeration of Antimatroids, part III

Let us continue the fun we had before here.

How do we speed up the calculation? Well, we need to limit somehow the space on which we perform the search.
Very obvious way is to eliminate the symmetries. Every permutation $\pi \in S_n : \{0,1\ldots,n-1\} \to \{0,1\ldots,n-1\}$ induces a natural transformation on sets (and sets of sets, like antimatroids, …). For example:
$\sigma = (120) = \{ 0 \to 1; 1 \to 2; 2 \to 0 \}$
working on :
$F = \{ \{\}, \{0\}, \{0,1\}, \{0,2\}, \{0,1,2\} \}$
gives:
$\sigma(F) = \{ \{\}, \{1\}, \{1,2\}, \{1,0\}, \{1,2,0\} \} = \{ \{\}, \{1\}, \{1,2\}, \{0,1\}, \{0,1,2\} \}$
1, 1, 3, 22, 485, 59386, ...