# 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\} \}$

So if we can now say that $F$ and $\sigma(F)$ are isomorphic.
We can also define:
$Aut(F) = \{ \sigma : \sigma(F)=F \}$ (the set of self-symmetries).

What we want to do, is eliminate every symmetric duplicates, and keep only one representative from every family of isomorphic antimatroids.
But instead of trying for every pair of antimatroids trying to decide if they are isomorphic, we can find minimal representative under some ordering from whole family of isomorphic ones.

DAG of antimatroids after the duplicates were eliminated.

How do we implement it?
First, the simpler approach.

vector start;
for(int i=0;i<n;<span class="hiddenGrammarError">i++)
start.push_back(i);
do
{
perms.push_back(start);
}
while(next_permutation(start.begin(),start.end()));
psize = perms.size();

ap.resize(N, vector(psize));
for(int p=0;p<psize;p++)
for(int i=0;i
ap[i][p] = apply(perms[p], i);


and

int apply(vector p, int x)
{
int y = 0;
for(int i=0;i
if(x & (1<<i))
y |= 1<<p[<span class="hiddenGrammarError">i];
return y;
}


first we keep for convenience enumerated every permutation from $S_n$,
apply just lifts the permutation into a function $2^n \to 2^n$, and ap[][] is just a memoization of this function. This way, applying p-th permutation on bitmask representing antimatroid reduces to:

u128 R;
for(int i=0;i
if(U.getbit(i))
R.setbit(ap[p][i]);
return R;


but we really don’t need such a function.

What we really need, is this:

pair<u128,vector > _reduce(const u128& X)
{
...
}
u128 reduce(const u128& X)
{
return _reduce(X).first;
}
vector aut(const u128& X)
{
return _reduce(X).second;
}


As we will soon see, we will get as a side effect both a minimal isomorphic bitmask (antimatroid) and a list of all self-symmetries.
And we will fill the body of _reduce as follows:

2. we will iterate over every bit of output, trying to make him smallest possible (in fact, largest, but it doesn’t matter), while not changing previous bits already set
3. doing this, we will eliminate those permutations that were not optimal on currently processed bit
pair<u128,vector > _reduce(const u128& X)
{
u128 R;
vector C(psize);
for(int i=0;i
C[i]=i;
vector<int> nC;
int i=1;
for(int i=0;i<(1<<n);i++)
{
nC.clear();
bool v = false;
for(auto& t : C)
{
bool nv = X.getbit(ap[i][t]);
if(nv > v)
{
nC.clear();
v = nv;
R.setbit(i);
}
if(nv == v)
{
nC.push_back(t);
}
}
swap(nC,C);
}
return make_pair(R,C);
}


Now we need to plugin those functions somewhere in the working code.

When iterating over a new antimatroids, we increased ans += 1.
And now we need to do:

    for(auto& S : P)
{
vector automorph = aut(S);
ans += psize/automorph.size();


We need in fact to sum $\sum_F \frac{|S_n|}{|Aut(F)}$ (because of orbit-stabilizer theorem).

And another small correction is when inserting newly found antimatroid into hashtable, we did:
 nL.insert(nS); 
and now we do:
 nL.insert(reduce(nS)); 

OK, lets try the code (as a bonus, we get the number of non-isomorphic antimatroids):

$time ./symm 133059751 199572 real 0m24.442s user 0m22.085s sys 0m1.940s  22s over previous 1014s! Can we perform symmetry elimination in a more efficient way? If we keep in mind that for most antimatroids, $|Aut(R) = 1$, yes. Right now we’re starting with a list of $n!$ permutations, and successfully eliminate unnecessary ones. But with bits of output, we have them in states ‘0’, ‘1’ and undecided (the ones which we still don’t process). Maybe we can operate on similarly nondeterministic permutations? We would like to start with a permutation of the form: (undecided, undecided, …, undecided), and gradually fill the prefix with values. We are in a comfortable position, because of the way we enumerate our permutations (for example for $n=4$): perms[0]={0,1,2,3} perms[1]={0,1,3,2} perms[2]={0,2,1,3} perms[3]={0,2,3,1} perms[4]={0,3,1,2} perms[5]={0,3,2,1} perms[6]={1,0,2,3} perms[7]={1,0,3,2} perms[8]={1,2,0,3} perms[9]={1,2,3,0} perms[10]={1,3,0,2} perms[11]={1,3,2,0} ...  All permutations that share common prefix of length $k$ take contiguous set of indices (of length $(n-k)!$). To represent partial permutation, we will just keep first of the representatives, and number of prefix already in place. Second fact that helps us, is: to know the value of ap[mask][perm], if $mask<2^k$, we only need to know first k values of perm. Why? If $mask<2^k$, then only first k bits of mask can be equal to 1, so we only need to know first k values of perm to know where those 1 will be moved. pair<u128,vector > _reduce(const u128& X) { u128 R; vector<int> C = {0}; vector<int> nC; C.reserve(psize); nC.reserve(psize); R.setbit(0); int i=1; for(int bit=0;bit<n;bit++) { int ss = C.size(); C.resize(ss*(n-bit)); for(int it=ss;it<ss*(n-bit);it++) C[it] = C[it-ss]+factorial[n-1-bit]; for(;i<(1<<(bit+1));i++) { nC.clear(); bool v = false; for(auto& t : C) { bool nv = X.getbit(ap[i][t]); if(nv > v) { nC.clear(); v = nv; R.setbit(i); } if(nv == v) { nC.push_back(t); } } swap(nC,C); } } return make_pair(R,C); }  We start with only one permutation, 0, with meaning {undecided,undecided,…,undecided}. We iterate over 0<i<N, and every power of two, we replace all alive permutations with copies with one more value set, every valid combination. In the worst case, previously we could make $N \cdot n! = 2^n \cdot n!$ operations (every permutation was valid and kept all around the place), while now worst case is $2^{n-1} \cdot n! + 2^{n-2} \cdot \frac{n!}{2!} + 2^{n-3} \cdot \frac{n!}{3!} + ... \approx 2^n \cdot n! \cdot (e^{\frac{1}{2}}-1)$, so there is not much to gain there. But worst case is rarest one, only 1 antimatroid (full) has as many symmetries. For most common case, the gain could be huge, as we will be operating on relatively short lists all the time. Let us see: $ time ./symm2
133059751 199572

real	0m8.381s
user	0m6.164s
sys	0m2.068s


6s! That is a huge improvement.
In the next post I will show how to use parallelism, and results of actual computations for $n=7$.

(Source code available: code1, code2)

edit:
Exercise: I lied a little when saying that aut() returns list of automorphisms. Can you spot it? Can you say what exactly this function really returns? Can you argue why it doesn’t change the correctness of the code?