A linear extension of a Partially Ordered Set is a Permutation of the elements , , ... of such that Implies . For example, the linear extensions of the Partially Ordered Set 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.