Counting number of permutations respecting partial order Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c_{ij} \in \{-1, 0, 1\}$ where $0$ represents unknown and $-1, 1$ represent $A_i &lt; A_j$ and $A_i \geq A_j$ respectively.

Is there an efficient algorithm that counts the number of partitions of $A$ that respect the partial order? E.g. for the all-zero matrix (totally undefined partial order) it's simply $n!$ and for a matrix  containing a total order it's simply $1$.

We can assume that the partial order does not contain contradictions, e.g. we won't have $A_i &lt; A_i$ or some chain of comparisons that violates transitivity.
Brightwell and Winkler proved that this program is #P-complete in their paper Counting linear extensions. You can, however, estimate the number of linear extensions efficiently.