Menu
How to efficiently enumerate all partial orders on a finite set?
I want to check whether a partial order with specified properties exists. To check this I am going with brute force to enumerate all possible partial orders on small finite sets.
404
A partial order relation is a homogeneous relation that is transitive and antisymmetric. There are two common sub-definitions for a partial order relation, for reflexive and irreflexive partial order relations, also called "non-strict" and "strict" respectively.
A partial order on a set S is a relation ⪯ on S that is reflexive, anti-symmetric, and transitive. The pair (S,⪯) is called a partially ordered set . So for all x, y, z∈S: x⪯x, the reflexive property. If x⪯y and y⪯x then x=y, the antisymmetric property.
Another classic example of partial ordering is the subset relation, denoted ⊆, on ℘(S), where S is any set of elements. Observe that S can be empty, in which case ℘(∅)={∅}, and (℘(∅),⊆) is obviously a partially ordered set.
To determine the partial order of O2, note that doubling the concentration of O2 also doubles the rate of the reaction. This may be mathematically expressed as: For the equality to hold true, x must equal 1. This makes the partial order for O2 first order.
They will have to be really small finite sets for your project to be practical.
The number of labelled posets with n labelled elements is Sloane sequence A001035, whose values are known up to n=18:
0 1
1 1
2 3
3 19
4 219
5 4231
6 130023
7 6129859
8 431723379
9 44511042511
10 6611065248783
11 1396281677105899
12 414864951055853499
13 171850728381587059351
14 98484324257128207032183
15 77567171020440688353049939
16 83480529785490157813844256579
17 122152541250295322862941281269151
18 241939392597201176602897820148085023
Sequence A000112 is the number of unlabelled posets; unsurprisingly, the numbers are smaller but still rapidly grow out of reach. They seem to be known only up to n=16; p16 is 4483130665195087.
There is an algorithm in a paper by Gunnar Brinkman and Brendan McKay, listed in the references on the OEIS A000112 page, linked above. The work was done in 2002, using about 200 workstations, and counting the 4483130665195087 unlabelled posets of size 16 took about 30 machine-years (the reference machine is a 1 GHz Pentium III). Today, it could be done faster but then the value of p17 is presumably about two decimal orders of magnitude bigger.
133
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
