There is a combinatorial structure called matroid which generalizes the notion of linear independence. Having a matroid on a set \(E\) is equivalent to having a rank function.
A rank function on a set \(E\) is a function \(r\colon 2^E\to \mathbb{N}\) such that
for every \(A,B\in 2^E\).
Today, I would like to count the number of matroids on a fixed set \(E\) of a fixed size \(n\). This number is given by A058673 on OEIS. I am going to use a brute-force-search for functions satisfying conditions (2) and (3) in the space of functions that satisfies only the condition (1) above. The complexity is horrendous \(\mathcal{O}(4^n)\).
Well… I am going to implement this in C.
Let us start with the includes:
#include<stdio.h>
#include<stdlib.h>I am going to implement functions of the type \(2^E\to\mathbb{N}\) as an array of positive integers. Now, a function that tests if conditions (2) and (3) are satisfied:
unsigned short is_valid(unsigned short *r, unsigned short n) {
unsigned short i, j;
// Check monotonicity
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
if(r[i] > r[i|j])
return(0);
// Check submodularity
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if(r[i|j] + r[i&j] > r[i] + r[j])
return(0);
return(1);
}Having two consecutive loops look bad, but notice that there is a return statement in the loops. This usually is cut short.
Next, I am going to write a function that will iterate over all arrays of length \(2^{|E|}\) modeling all functions of the specified type with condition (1) above. But first I would need a function that counts the number of 1’s in the binary representation of an integer \(m\). This will model \(|A|\) for an element \(A\in 2^E\). I am using Kernighan’s Algorithm.
unsigned short count_ones(unsigned short m) {
unsigned short i, count = 0;
for(i=m; i>0; i&=(i-1))
count++;
return count;
}Next, the iteration function:
unsigned short *iterate(unsigned short *r, unsigned short n) {
unsigned short i, m;
for(i=n-1, m=count_ones(n-1);
i>0 && r[i]==m;
--i, m=count_ones(i))
r[i]=0;
if(i) {
++r[i];
return(r);
}
return(NULL);
}Now, the driver function:
int main(int argc, char *argv[]) {
unsigned short *r, N;
unsigned long result = 0;
if(argc<2) {
printf("Usage %s n.\n", argv[0]);
return(0);
}
// |E| = n and N is 2^n = # of subsets of E
N = 1<<atoi(argv[1]);
r = calloc(N, sizeof(unsigned short));
do
if(is_valid(r,N))
++result;
while(r=iterate(r,N));
free(r);
printf("%d\n", result);
return(0);
}The results are
| N | Result | Time |
|---|---|---|
| 0 | 1 | 2ms |
| 1 | 2 | 2ms |
| 2 | 5 | 2ms |
| 3 | 16 | 2ms |
| 4 | 68 | 1540ms |
Didn’t even try \(N=5\).