We are given a set of comparisons of the form
z[i] < z[j] for various
j and an unknown permutation
z of length
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.