# topological sort of partial order into sorted sets

Given a partial order of elements, one can use topological sorting to produce a sorted list of elements. For example, if we have the partial order A->B and A->C, then the possible topological sort results are [A,B,C] and [A,C,B].

I am interested in producing a sorted list of sets [$S_1, \ldots, S_k$] that satisfy the partial order (The sets $S_i$ partition the elements). Here, the requirements are:

1. for $i = 1 \ldots k-1$, $\exists e_1 \in S_i,e_2 \in S_{i+1}$ s.t. $e_1 < e_2$

2. for each set $S_i$, $\nexists e_1, e_2 \in S_i$ such that $e_1 < e_2$ or $e_2 < e_1$

In our example, the only correct sorted list of sets is [{A},{B,C}]. Given a partial order, how many possible sorted lists of sets exist? Is there a name for this kind of sorting? Any pointers are appreciated.

-
If condition (1) is strengthened to $e_1 < e_2$ for all $e_1 \in S_i,\, e_2 \in S_{i+1}$ then there is no correct answer for $\{a,b,c\}$ partially ordered by $a<b$. That's why Steven relaxed it to its current state. –  Yuval Filmus Apr 15 '11 at 1:18

First, we can deduce from 1. and 2. the condition

3. for $i\le j$, $\nexists e_1\in S_i, e_2\in S_j$ such that $e_2<e_1$.

(If there were such elements, we could use a chain of elements provided by 1. to find elements contradicting 2. by transitivity.)

It follows that the list must be exactly as long as the longest chain(s). If it were any shorter, there would have to be elements in each longest chain contradicting 3. If it were any longer, 1. would imply the existence of a longer chain.

This suggests an algorithm for forming all possible sorted lists of sets. For each element $e$, let $l_e$ be the length of the longest chains in which $e$ occurs, and let $m_e$ be the index at which it occurs in these chains, i.e. $m_e=1$ if $e$ is the least element in these chains and $m_e=l_e$ if it is the greatest. The index $m_e$ is well-defined, since any two chains with different $m_e$ would yield a chain of length greater than $l_e$.

Now order the elements using the lexicographical order according to $(l_e,m_e)$, i.e. $d<e \Leftrightarrow l_d < l_e \lor (l_d = l_e \land m_d < m_e)$, and start with the greatest elements. The beginning is easy: $k$ has to be the greatest value of $l_e$, and there is only one possible placement for elements with that value of $l_e$ -- they have to go in $S_{m_e}$.

Then things get slightly more complicated. Each chain of length $l$ considered by itself can be placed in $\left(k\atop l\right)$ different ways, but there may be links between the chains that constrain their relative placement. To recursively generate all possible lists, you can go through the elements in the above order and place each element $e$ in all sets that are still allowed. Originally, the allowed sets will be $S_i$ with $m_e \le i \le m_e+k-l_e$. This may be further constrained by the placement of the immediate successors of $e$ in chains of length $l_e$, since $e$ must be placed below each of them, but the lexicographical ordering guarantees that there are no further constraints beyond these, so they're easy to keep track of.

So this is relatively straightforward to implement as an algorithm, but since the cross-constraints between the chains can be arbitrarily complicated, I think you're unlikely to find a nice expression for the number of possible lists.

-