In one of my classes, there is a type of problem that comes up where, after doing some calculations and coming up with some abstractions, it looks like this:
Given a set of objects and some conditions, find all valid orderings of these objects.
Example:
A B P Q X Y
A must come before B. P must come before Q. X must come before Y. How many valid orders are there of the six objects?
Here was how I solved it:
There are 3 valid starting letters: A, P, and X. So if we find how many orderings there are starting with A, we multiply that by 3 to get the answer.
Starting with A: valid second letters are B, P, X
Suppose second letter is B: 6 valid orders (I calculated this by hand instead of going deeper in recursion)
Suppose second letter is P: 12 valid orders (6 with X as third letter, 3 with Q, 3 with B)
Suppose second letter is X: 12 valid orders
This gives a total of 30 orders for starting with A and 90 orders total. I think, I could be missing some.
The letters are indistinguishable, so there are an equal number of combinations where A is before B than after; likewise with the others. And the conditions are independent, so we can impose them separately. Therefore there are 6! / (222) = 90 combinations.
Yep, I tried to be explicit that the conditions must be independent, but it’s worth repeating. An obvious case where it doesn’t work would be “A before B, B before P, and P before A”–clearly, no combinations can fit those conditions.
Also, to elaborate on what I meant by indistinguishability: with letters of ABPQXY, we can swap any two letters and have the same result (since the initial order doesn’t matter). But if we had AAABPQXY, this is no longer true, since that is very different from (say) BBBAPQXY.
For those conditions, it’s easier to count the number of permutations that don’t satisfy the restriction and subtract from the total number. You just have to be careful with that method, as you can easily get into some nasty inclusion-exclusion calculations.
The general problem you’re trying to solve is that of counting the linear extensions of a partial order. This is #P-complete in the general case, so if your constraints form a generic partial order you can’t expect to find an efficient solution. But in the case where the constraints separate into several small disjoint graphs (as with your examples) you can count the linear extensions separately for each component (by brute force, if you like) and then fold them together arbitrarily; this is what Dr. Strangelove’s solution does.
So for example if you have three components, with v[sub]1[/sub], v[sub]2[/sub], and v[sub]3[/sub] objects, and n[sub]1[/sub], n[sub]2[/sub], and n[sub]3[/sub] linear extensions, then there are
n[sub]1[/sub] n[sub]2[/sub] n[sub]3[/sub] (v[sub]1[/sub]+v[sub]2[/sub]+v[sub]3[/sub])!/(v[sub]1[/sub]!v[sub]2[/sub]!v[sub]3[/sub]!)
orderings consistent with the constraints; the factor with the factorials just counts the number of ways of folding these independent orderings together.
In your first example, each component has v[sub]i[/sub]=2 and is already a linear order, so counting the linear extensions is trivial, n[sub]i[/sub]=1. Your second example (A<B<X) is also a linear order. LSLGuy’s example has an incomplete ordering (A<B, A<X<Y) so that’s a case where the counting is not trivial.
If these are the only two restrictions, it’s also easy enough: Take all the orderings, and divide by 3! (each relative ordering of A, B, and X is equally as likely to come up as any other, and there are 3! relative orderings of A, B, and X, out of which only 1 (A before B before X) is acceptable).
It’s not quite possible to say how difficult the general problem you’re trying to solve is, unless and until the general problem is fixed in concrete detail (after all, just from having said two particular problems you might be interested in, there are many different generalizations possible). Sure, there’s some kind of general problem of which these are instances which is difficult to solve, but it may well turn out that the only kinds of problems you actually care about are more restricted such that they are easy to solve.
Fortunately I figured that out on my own (in that cast dividing by 3!) and I was able to solve all of the problems, since they were of a fairly manageable scale. I can see how this would become a very complicated problem for high n and large numbers of dependent conditions!