Generating Linear Extensions Fast
Gara Pruesse, Department of Computer Science,
University of Toronto.
Frank Ruskey, Department of Computer Science,
University of Victoria.
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 #P-complete.
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(n2 + e(P)).
- The postscript file
is 230K bytes, the dvi file
is 71K bytes.
- Appeared in SIAM J. Computing, Vol. 23, No. 2, pp. 373-386, April 1994.
- Gara Pruesse was at the University of Vermont, but now I've lost
track of her whereabouts.
- An implementation is available,
- 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) 185-204.
E.R. Canfield and S.G. Williamson, A loop-free algorithm
for generating the linear extensions of a poset,
Order, 12 (1995) 57-75.
D. Rasmussen, C.D. Savage, and D.B. West,
Gray Code Enumeration of Families of Integer Partitions,
J. Combinatorial Theory (A), 70 (1995) 201-229.
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 ACM-SIAM Symposium on
Discrete Algorithms (SODA), pages 350-354, San Francisco, California,
25-27 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.
Gang Wang, Wenrui Gong, and Brian DeRenzi, and Ryan Kastner,
Ant Colony Optimizations for Resource and Timing Constrained
Instruction Scheduling, IEEE Transactions on Computer-aided
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 19-21, 2005, pp. 98-105.
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
food-web data, in the book:
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 Multi-indicator Systems
- An Integrative View with a Look Forward,
Environmental and Ecological Statistics, 2011, Volume 5,
291-303, DOI: 10.1007/978-1-4419-8477-7_18
to Frank Ruskey's publication list.