Abstract
A precise concept of when a combinatorial counting problem is “hard” was first introduced by Valiant (1979) when he defined the notion of a #P-complete problem. Correspondingly, there has been consistent interest in the notion of when a combinatorial listing problem admits a very special regular structure in which transition times between objects being listed are uniformly bounded by a fixed constant. Early descriptions of suchloop-free listing algorithms may be found in the bookAlgorithmic Combinatorics by Even (1973). Recently, the problem of counting all linear extensions of a partially ordered set has received attention with regard to both of these combinatorial concepts. Brightwell and Winkler (1991) have shown, by a very ingenious argument, that the poset-extension counting problem is #P-complete. Pruesse and Ruskey (1992) have shown that the corresponding listing problem can be solved in constant amortized time and have posed the problem of finding a loop-free algorithm for the poset-extension problem. The present paper presents a solution to this latter problem. This sequence of results represents an interesting juxtaposition, in a fixed, naturally-occurring combinatorial problem, of intricate and precisely defined “irregularities” with respect to counting with very strong regularities with respect to listing.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A., Hopcroft, J., and Ullman, J. (1974)The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass.
Brightwell, G. and Winkler, P. (1991) Counting linear extensions,Order 8, 225–242.
Ehrlich, G. (1973) Loopless algorithms for generating permutations, combinations, and other combinatorial configurations,J. Assoc. Comput. Mach. 20, 500–513.
Even, S. (1973)Algorithmic Combinatorics, The Macmillan Company, New York.
Gray, F. (1953) Pulse code communication,U.S. Patent 2632058.
Hopcroft, J. E. and Ullman, J. D. (1979)Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass.
Joichi, J. T., White, D. E., and Williamson, S. G. (1980) Combinatorial Gray codes,SIAM J. Computing 9, 130–141.
Johnson, S. M. (1963) Generation of permutations by adjacent transpositions,Mathematics of Computation 17, 282–285.
Knuth, D. (1966)The Art of Computer Programming, Vol. II, Addison-Wesley, Palo Alto.
Koda, Y. and Ruskey, F. (1993) A Gray code for the ideals of a forest poset,J. Algorithms 15, 324–340.
Pruesse, G. and Ruskey, F. (1994) Generating linear extensions fast,SIAM J. Computing 23, 373–386.
Trotter, H. (1962) Algorithm 115: Perm.,Communications of the ACM 5, 434–435.
Valiant, L. (1979) The complexity of computing the permanent,Theoretical Computer Science 8, 189–201.
Wilf, H. (1977) A unified setting fjor sequencing, ranking, and selection algorithms for combinatorial objects,Advances in Math. 24, 281–291.
Wilf, H. (1989) Combinatorial algorithms: An update, inCBMS-NSF Regional Conf. Series in Appl. Math. SIAM, Philadelphia.
Williamson, S. G. (1988)Combinatorics for Computer Science, Computer Science Press, Rockdale, MD.
Author information
Authors and Affiliations
Additional information
Communicated by I. Rival
Research supported by the National Security Agency.
Rights and permissions
About this article
Cite this article
Canfield, E.R., Williamson, S.G. A loop-free algorithm for generating the linear extensions of a poset. Order 12, 57–75 (1995). https://doi.org/10.1007/BF01108590
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01108590