Enumerate all partial orders
Asked Answered
A

1

9

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.

Amorous answered 22/4, 2013 at 20:4 Comment(13)
Not gonna happen. There are exponentially many.Rubino
related: math.stackexchange.com/questions/232613/…Hydra
@G.Bach- Even if there are exponentially many objects, you can still enumerate all of them. It just might take a while.Lowery
@Lowery He asked for efficiency; the way I know it, that usually refers to total execution time being polynomial.Rubino
@G.Bach- I suppose that's true. You could consider trying to generate combinatorially many items efficiently by saying that "efficiency" means "polynomial overhead for each item," though.Lowery
@Lowery I guess that would be the concept that is known as polynomial delay?Rubino
Interestingly, a Google search for this doesn't seem to turn up anything. Knuth Volume 4A doesn't seem to cover it and it doesn't appear that it's planned to be in any other part or Volume 4. This strikes me as a problem that must have been attacked before, but I can't find any evidence of this. I hope someone knows how to do this!Lowery
It may help to know what properties you are looking to satisfy. If they are nice, they could limit your search to a polynomial-sized sub-space.Agile
I don't know much about posets but would this example be a correct enumeration? (Haskell GHCi): Prelude Data.List> concatMap permutations . subsequences $ ["x","y","z"] which would enumerate: [[],["x"],["y"],["x","y"],["y","x"],["z"],["x","z"],["z","x"],["y","z"],["z","y"],["x","y","z"],["y","x","z"],["z","y","x"],["y","z","x"],["z","x","y"],["x","z","y"]]Auscultation
@groovy Posets are sets together with relations, meaning subsets of YxY for some set Y. So for [x,y,z], all posets would require a subset of [x,y,z]² as the partial ordering relation.Rubino
@G.Bach I see...it's not that simple. I think this may be the article rici refers to in his answer: cs.anu.edu.au/~bdm/papers/posets.pdfAuscultation
@Amorous I suggest you give us a bit more detail about what it is you are trying to do.Gastrology
@groovy- Can you post that as an answer? That's pretty much the perfect resource for answering this question.Lowery
T
13

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.

Tillio answered 22/4, 2013 at 23:32 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.