<p>As far as I can tell, your problem is equivalent to the following: given a partial order (represented by its comparability pairs, which forms a DAG), count how many linear extensions it has.</p>
<p>This problem is known to be #P-hard, see Brightwell and Winkler, &quot;Counting Linear Extensions&quot;, Order, 1991. It is #P-hard even in quite restricted cases, e.g., <a href="https://arxiv.org/abs/1802.06312" rel="noreferrer">https://arxiv.org/abs/1802.06312</a></p>

CC BY-SA 4.0
2022-11-01T22:18:46.557Z
Perhaps it is useful to add that there are exceptions when considering restricted classes of partial orders. N-free posets (series-parallel partial orders) have a poly-time solution to count the number of linear extensions.
ExpressionCoder
CC BY-SA 4.0
2022-10-13T09:32:08.790Z
2022-10-13T09:32:08.790Z
Antoine Amarilli 'a3nm'
<p>We are given a set of comparisons of the form <code>z[i] &lt; z[j]</code> for various <code>i</code> and <code>j</code> and an unknown permutation <code>z</code> of length <code>n</code>.</p>
<p>We can assume those are transitively closed, or compute the closure relatively quickly by Floyd-Warshall.</p>
<p>Is there an efficient algorithm to determine the number of permutations compatible with the known comparisons? We can of course backtrack our way to the answer, but this would be quite slow.</p>
<p>The constraint we have looks like a forest of DAGs. It seems that by carefully counting the ways in which it can be collapsed into a line, we might get to the answer more directly.</p>

CC BY-SA 4.0
2022-10-14T19:10:11.437Z
As @a3nm mentions this is intractable for many comparisons, but there is likely a $poly(n) 2^{poly(k)}$ algorithm for $k$ comparisons, which would be much faster than brute force for small $k$.
Geoffrey Irving
CC BY-SA 4.0
2022-10-14T21:20:33.600Z
I've also found out that simple Markov chain over the set of linear extensions can mix very quickly making it practical to sample for them. Given that I'm after the average number of inversions among extensions, this is perfect for me.
Arthur B
CC BY-SA 4.0
2022-10-14T22:19:16.310Z
Although #P hard, it can be approximated (has a PTAS) via convex volume estimation.
mic
CC BY-SA 4.0
2022-10-16T06:23:52.173Z
I understand it involves 
Arthur B
<co.combinatorics><sorting><permutations><topological-sorting>
Number of permutations that satisfy a given set of comparisons
Arthur B
# Number of permutations that satisfy a given set of comparisons

(Asked by: username_0 on 2022-10-13)

We are given a set of comparisons of the form `z[i] < z[j]` for various `i` and `j` and an unknown permutation `z` of length `n`.

We can assume those are transitively closed, or compute the closure relatively quickly by Floyd-Warshall.

Is there an efficient algorithm to determine the number of permutations compatible with the known comparisons? We can of course backtrack our way to the answer, but this would be quite slow.

The constraint we have looks like a forest of DAGs. It seems that by carefully counting the ways in which it can be collapsed into a line, we might get to the answer more directly.

**Tags:** co.combinatorics, sorting, permutations, topological-sorting
> **Comments:**
> **username_1**: As @a3nm mentions this is intractable for many comparisons, but there is likely a $poly(n) 2^{poly(k)}$ algorithm for $k$ comparisons, which would be much faster than brute force for small $k$.  
> **username_0**: I've also found out that simple Markov chain over the set of linear extensions can mix very quickly making it practical to sample for them. Given that I'm after the average number of inversions among extensions, this is perfect for me.  
> **username_2**: Although #P hard, it can be approximated (has a PTAS) via convex volume estimation.  
> **username_0**: I understand it involves   

---

## 1 answers

### Answer by username_3 on 2022-10-13. Score: 12 | Accepted answer

As far as I can tell, your problem is equivalent to the following: given a partial order (represented by its comparability pairs, which forms a DAG), count how many linear extensions it has.

This problem is known to be #P-hard, see Brightwell and Winkler, "Counting Linear Extensions", Order, 1991. It is #P-hard even in quite restricted cases, e.g., <https://arxiv.org/abs/1802.06312>

> **Comments:**
> **username_4**: Perhaps it is useful to add that there are exceptions when considering restricted classes of partial orders. N-free posets (series-parallel partial orders) have a poly-time solution to count the number of linear extensions.  

---

