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

But first, let us fix the universum to be: S = \{0,1,\ldots,n-1\}.

Ok, so how do we start? By… ignoring the observation (2). Basically, the procedure to generate the unique father in the DFS tree looks very costly:

Proof sketch: Let U be the union of the sets in A, and by removing elements one at a time from U find T and x such that the sets between T u {x} and U form a powerset but the sets between T and U do not. If U \ {x} is in A, then one can continue recursively in the subantimatroid between T and U \ {x}; otherwise we can choose S to be a one-element extension of the largest set in A between T and U \ {x}.

(Ok, I admit, I am lazy and it looks complicated..)

So, if we have no way to prevent duplicates, we have to detect them by ourselves. So we will traverse the DAG of antimatroids (it is no longer a tree) with a BFS algorithm. We will process at one time every antimatroid of size k, and generate all of size k-1, starting with the maximal one, of size 2^n (minimal possible size is n+1, and there are n! different minimal ones).

antimatroids2

DAG of antimatroids for n=3.(tree edges in bold)

So, let’s do some coding here!
Every antimatroid will be represented just as a bitmask, with N=2^n bits. If we want to crank n=6,7, we need 128-bit type. Some architectures and C++ compilers have them, but I was in unfortunate position not to have. So I quickly wrote

class u128
{
    public:
        unsigned long long low;
        unsigned long long high;
...

with all important bitset functions, |, &, ~, …
(looking from a perspective, I could use bitset, but what’s done was done..)

Our structure of a program would be:

u128 seed;
for(int i=0;i
vector L(1,seed); //one bitmask with N bits on
unsigned long long ans = 0;
while(!L.empty())
{
    ans += L.size();
    cerr << L.size() << endl;
    L = onestep(L);
}
cout << ans << endl;

So, only part missing is the magic of onestep().

How do we process single antimatroid?
We could just try to remove every possible bit, and test if the candidate is a valid antimatroid after this.
But this seems like a unnecessary effort, so let us just try and generate every valid candidate for removal at once (preferably in one big bitmask).
So we should look for bits that are on, but:

  1. when removed, would violate set union closedness
  2. or, would violate accessibility

We can solve (1) considering minimal generating set for given family of sets that makes one anitmatroid.
If we consider following operations on family of sets:
S(F) = \{ u \cup v : u \in F, v \in F, u \not\subseteq v, u \not\supseteq v \} (every set that can be obtained as nontrivial sum of two sets from F)
S'(F) = S(F) \cup F (as above, but also the trivial ones)
then minimal fixed point of operation S' is closure under set sum. (it really mean iterating S'(S'(S'(\ldots S'(F)\ldots ))) until nothing new can be added)

So given any family of sets, we can take a closure. And it works other way around:
H = F - S(F) will be minimal generating set (I’ll omit proof).

In terms of code:

u128 mask;
for(int I=1;I<N-1;I++)
    if(S.getbit(I))
        for(int J=1;J<I;J++)
            if(S.getbit(J))
                if((I|J) != I && (I|J) != J)
                    mask.setbit(I|J);
mask = S & ~mask;

Ok, so for (2), we can precompute, for every pair of values between 0, N, if they differ on just one bit. In fact, we can generate it as a boolean matrix N\times N:

vector pred(N);
vector succ(N);
for(int I=0;I<N;I++)
    for(int i=0;i
        if(I & (1<<i))
            pred[I].setbit(I & ~(1<<i));
        else
            succ[I].setbit(I | (1<<i));

pred[I][J] keeps information if J is smaller by exactly one bit than I, and succ[I][J] if J is larger by one bit than I.

We can think of this in terms of supporting relation.
If bits I and J are on in S, and I is smaller by 1 bit than J, then I is supporting J. In a valid antimatroid (mask), every set (bit) has to be supported, except from \{\} (0th bit).
It is easy to test if given bitmask S passes the condition (2):

u128 succ_closure;
for(int I=0;I<N;I++)
    if(S.getbit(I))
        succ_closure |= succ[I];
succ_closure.setbit(0);
assert((succ_closure & S) == S);

(if we consider succ as a matrix, vector (S) \times matrix (succ) multiplication, but instead of +, \times, we have \vee, \wedge)

It is a little bit harder to get every position that could violate supporting condition. First, we need to generate every position, that is supported by exactly one other position. How to do this? Well, we could get every position that is supported by at least one position, and substract all that are supported by more than one:

u128 f1,f2;
for(int I=0;I<N;I++)
    if(S.getbit(I))
    {
        f2 |= succ[I] & f1;
        f1 |= succ[I];
    }
u128 R = f1 & ~f2 & S;

Now, R contains all the bits supported by exactly one other bit.
What to do next? Well, now we will use the prev matrix, with the same vector \times matrix binary multiplication.

for(int I=0;I<N;I++)
    if(R.getbit(I))
        mask = mask & ~pred[I];

After all of this trickery, mask should contain only bits that are OK to switch off to get smaller antimatroid. Now we can happily iterate over them, and put those masks into hashtable, that will eliminate all the duplicates for us.

Let us see how is it running!

For n=5, it gives:

$time ./run1
59386

real	0m1.723s
user	0m0.756s
sys	0m0.912s

So, it gave correct answer (yes, I verified, for all smaller n it was also correct!)

Can we try it with n=6?

$time ./run1
133059751

real	17m26.972s
user	16m54.863s
sys	0m9.221s

So we have another term!
Also, interesting are the numbers of antimatroid of fixed size (we get them here as a byproduct of computation).

1
6
30
75
240
690
1806
4070
8370
15600
27960
47712
80190
130710
209220
325830
493986
729210
1046220
1454400
1959540
2561607
3245430
3973170
4698510
5367570
5947746
6408015
6751640
6976140
7111290
7157832
7132710
7015665
6813540
6509370
6135150
5686830
5190030
4635450
4043220
3415980
2790720
2181120
1627260
1150770
777330
500760
310380
183980
105240
58020
30960
15960
8010
3960
1800
720

We start with 1 antimatroid of size 64, and end with 720=6! antimatroids of size 7.

Can we try this approach to get the answer for n=7? Not really.
If we use some numerology of double exponential growth we expect here, we can observe that the logarithm of answer grows exponentially, by 1.7 at each step. That gives expected answer around \approx 6\cdot 10^{13}. With some huge CPU available it could be doable, but the problem lies in ability to store groups of 128bit = 16byte bitmasks containing around 10^{12} elements at once.
In following post I will show how to work around it!

(Sourcecode used above is available here.)

Advertisements

6 responses to “Enumeration of Antimatroids, part II

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

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

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

  4. I think you should replace < with < in several places in the article (and & instead of &), because the code looks messed up!

  5. …and the damn coder of this comments plugin also didn’t get html entities correctly. Obviously I’ve meant & l t ; and & a m p ;

    • Can you point me to where should I replace and from what to what? ‘ ‘& l t’ or ‘& l t’ -> ‘<' ?
      And I admit, the editor messes it constantly, if you save a draft without properly closing enviroment, evertything inside is processed and '<' is replaced with '& l t' and so on..

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