Tag Archives: Permutation

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