Generating Linear Extensions Fast

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 #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(n² + 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, 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) 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. Addison-Wesley, 2005.
• 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: 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 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