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 induces a natural transformation on sets (and sets of sets, like antimatroids, …). For example:

working on :

gives:

So if we can now say that and are isomorphic.

We can also define:

(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.

How do we implement it?

First, the simpler approach.

We start with some useful preprocessing:

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 ,

`apply`

just lifts the permutation into a function , 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:

- we will start with every possible permutation marked as ‘alive’
- 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
- 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 (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, , yes.

Right now we’re starting with a list of 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 ):

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 take contiguous set of indices (of length ).

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 , we only need to know first k values of `perm`

.

Why?

If , 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 operations (every permutation was valid and kept all around the place), while now worst case is , 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 .

(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?

Pingback: Enumeration of Antimatroids, part II | ParaCombinatorics

Pingback: Enumeration of Antimatroids, part IV | ParaCombinatorics