🚀 go-pugleaf

           Department of Computer Science, University of Toronto
              (GB = Galbraith Building, 35 St. George Street)

       -------------------------------------------------------------

                               COMBINATORIES
                GB221, at 4:00 p.m., Monday 19 October 1992

                               Gara Pruesse
           Department of Computer Science, University of Toronto

             "Generating Linear Extensions by Transpositions"

The set of linear extensions of a partially ordered set (poset) have been
the subject of much recent research.  The problem of counting linear
extensions was proved to be #P-complete by Brightwell and Winkler (1991).

Generating all instances of an object is an interesting problem with
applications to testing hardware, software, and for hypothesis testing.
Generalized Gray Codes form a particularly nice generation scheme, because
instances that are close in the listing are also close in the sense that
the difference between them is small (for a given notion of measuring
difference).  The best possible running time for a generation algorithm is
constant amortized time; i.e., O(E), where E is the number of instances
generated.

Generating all instances of a #P-complete object is especially interesting,
because it may well be that generating them is the best way to count them.
It was an open question as to whether #P-completeness, which implies
counting is hard, also implies that generating is hard.   We settle this
question by giving a constant amortized time generation algorithm for the
linear extensions of a poset.

We survey results towards a conjecture of Ruskey which characterizes the
posets for which a certain kind of Gray Code generation scheme is possible.
This leads to a algorithm for generating the linear extensions of a poset
that is optimal up to constant factors, and, in fact, is fast in practice.
This algorithm remains the only known constant amortized time generation
algorithm for a #P-complete combinatorial object.

This is joint work with Frank Ruskey at the University of Victoria.