Generating Linear Extensions Fast
Gara Pruesse, Department of Computer Science,
University of Toronto.
Frank Ruskey, Department of Computer Science,
University of Victoria.
Abstract:
One of the most important sets associated with a poset
P is its set of linear extensions, E(P).
In this paper, we present an algorithm to generate all of
the linear extensions of a poset in constant amortized time;
that is, in time O(e(P)), where
e(P) = E(P).
The fastest previously known 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.
Our algorithm is the first constant amortized time algorithm
for generating a ``naturally defined'' class of
combinatorial objects for which
the corresponding counting problem is #Pcomplete.
Furthermore, we show that linear extensions can be
generated in constant amortized time where each extension
differs from its predecessor by one or two adjacent
transpositions. The algorithm is practical and can be
modified to efficiently count linear extensions, and
to compute P(x < y), for all pairs x,y, in time
O(n^{2} + e(P)).
Comments:
 The postscript file
is 230K bytes, the dvi file
is 71K bytes.
 Appeared in SIAM J. Computing, Vol. 23, No. 2, pp. 373386, April 1994.
 Gara Pruesse was at the University of Vermont, but now I've lost
track of her whereabouts.
 An implementation is available,
click here
to download.
 Many of the results found here have been
extended to the basic
words of an antimatroid.
Selected papers that refer to this paper:

C. Savage, M.B. Squire, and D.B. West,
Gray Code Results for Acyclic Orientations,
Congressus Numerantium 96 (1993) 185204.

E.R. Canfield and S.G. Williamson, A loopfree algorithm
for generating the linear extensions of a poset,
Order, 12 (1995) 5775.

D. Rasmussen, C.D. Savage, and D.B. West,
Gray Code Enumeration of Families of Integer Partitions,
J. Combinatorial Theory (A), 70 (1995) 201229.

D. Avis and K. Fukuda,
Reverse Search for Enumeration,
Discrete Applied Mathematics, 65 (1996), 21  46.

Russ Bubley and Martin Dyer,
Faster random generation of linear extensions,
Proceedings of the Ninth Annual ACMSIAM Symposium on
Discrete Algorithms (SODA), pages 350354, San Francisco, California,
2527 January 1998.

L. Huston, R. Sukthankar, R. Wickremesinghe, M. Satyanarayanan,
G. Ganger, E. Riedel, A. Ailamaki.
Diamond: A Storage Architecture for Early Discard in
Interactive Search, Proceedings of USENIX Conference on
File and Storage Technologies, 2004.

D.E. Knuth, The Art of Computer Programming, Volume 4,
Fascicle 2, Generating All Tuples and Permutations, Exercise 93.
AddisonWesley, 2005.

Gang Wang, Wenrui Gong, and Brian DeRenzi, and Ryan Kastner,
Ant Colony Optimizations for Resource and Timing Constrained
Instruction Scheduling, IEEE Transactions on Computeraided
Design of Integrated Circuits and Systems, submitted.

T. Udeshi and K. Tsui,
Assembly sequence planning for automated micro assembly,
Assembly and Task Planning: From Nano to Macro Assembly and Manufacturing,
2005. (ISATP 2005). The 6th IEEE International Symposium on.
July 1921, 2005, pp. 98105.

Proceso L. Fernandez, Lenwood S. Heath,
Naren Ramakrishnan, and John Paul C. Vergara,
Reconstructing Partial Orders from Linear Extensions,
in Proceedings of the Fourth SIGKDD Workshop on Temporal Data Mining:
Network Reconstruction from Dynamic Data, Aug 2006.

Ralph Freese, Jaroslav Jezek, and J.B. Nation,
Free Lattices, Volume 42 of Mathematical Surveys and
Monographs, AMS, 1995, ISBN 0821803891.

Andrew R. Solow,
Some random thoughts on the statistical analysis of
foodweb data, in the book:
Andrea Belgrano,
Aquatic Food Systems: An Ecosystem Approach,
Oxford University Press, 2005, ISBN 019856483X.

Rainer Bruggemann and Ganapati P. Patil,
Ranking and Prioritization with Partial Order for Multiindicator Systems
 An Integrative View with a Look Forward,
Environmental and Ecological Statistics, 2011, Volume 5,
291303, DOI: 10.1007/9781441984777_18
Back
to Frank Ruskey's publication list.