Enumerate all partial orders

Question

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.

Answer 1

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; p₁₆ 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 p₁₇ is presumably about two decimal orders of magnitude bigger.