Tag Archives: Breadth-first search

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\} \}
Continue reading

Advertisements

Enumeration of Antimatroids, part II

As explained before, we would like to extend the following sequence A119770 (don’t click, it will spoil all the fun!):
1, 1, 3, 22, 485, 59386, ...
Continue reading