GENERATING LINEAR EXTENSIONS FAST

One of the most important sets associated with a poset P is its set of linear extensions, E(P). This paper presents an algorithm to generate all of the linear extensions of a poset in constant amortized time, t hat is, in time O(e(P)), where e(P) = \E(P)\. The fastest previously k nown algorithm for generating the linear extensions of a poset runs in time O(n.e(P)), where n is the number of elements of the poset. The a lgorithm presented here is the first constant amortized time algorithm for generating a ''naturally defined'' class of combinatorial objects for which the corresponding counting problem is #P-complete. Furtherm ore, it is shown that linear extensions can be generated in constant a mortized time where each extension differs from its predecessor by one or two adjacent transpositions. The algorithm is practical and can be modified to count linear extensions efficiently and to compute P(x < y), for all pairs x, y, in time O(n2 + e(P)).