Linear Extension

A linear extension of a Partially Ordered Set $P$ is a Permutation of the elements $p_1$, $p_2$, ... of $P$ such that $i<j$ Implies $p_i<p_j$. For example, the linear extensions of the Partially Ordered Set $((1,2),(3,4))$ are 1234, 1324, 1342, 3124, 3142, and 3412, all of which have 1 before 2 and 3 before 4.

References

Brightwell, G. and Winkler, P. ``Counting Linear Extensions.'' Order 8, 225-242, 1991.

Preusse, G. and Ruskey, F. ``Generating Linear Extensions Fast.'' SIAM J. Comput. 23, 373-386, 1994.

Ruskey, F. ``Information on Linear Extension.'' http://sue.csc.uvic.ca/~cos/inf/pose/LinearExt.html.

Varol, Y. and Rotem, D. ``An Algorithm to Generate All Topological Sorting Arrangements.'' Comput. J. 24, 83-84, 1981.