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.

DAG of antimatroids after the duplicates were eliminated.

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 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:

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

Advertisements

2 responses to “Enumeration of Antimatroids, part III

  1. Pingback: Enumeration of Antimatroids, part II | ParaCombinatorics

  2. Pingback: Enumeration of Antimatroids, part IV | ParaCombinatorics

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s