Generating Linear Extensions Fast.
One of the most important sets associated with a poset  ${\cal P}$ is its set of linear extensions, $E({\cal P})$. This paper presents an algorithm to generate all of the linear extensions of a poset in constant amortized time, that is, in time $O(e(\cP))$, where |E(\cP)|$.  The fastest previously known algorithm for generating the linear extensions of a poset runs in time $O(n \! \cdot \! e(\cP))$, where $n$ is the number of elements of the poset. The algorithm presented here 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, it is shown 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 count linear extensions efficiently and to compute $P (x < y)$, for all pairs $x,y$, in time $O(n^2 e({\cal P}))$.
Introduction
. One definition of the adverb "fast" is "in quick succession"
(Webster's Collegiate Dictionary [1]). The purpose of this paper is to show that the
linear extensions of a partially ordered set (poset) can be generated fast; so fast,
in fact, that no algorithm can be faster, up to constant factors. Furthermore, the
constants involved are very small and our algorithms extend the practical range of
posets for which extensions can be generated and counted.
Linear extensions are of great interest to computer scientists because of their relation
to sorting and scheduling problems. For example, there are many NP-complete
one-processor scheduling problems with precedence constraints ([13]), and one obvious
way of solving such problems is by generating all linear extensions of the precedence
constraints and picking the best extension. Linear extensions are also of interest to
combinatorists because of their relation to counting problems ([2],[21]). Our results
can be used to efficiently generate standard Young Tableau of a given shape, alternating
permutations, and any of the many other combinatorial objects that can be
viewed as linear extensions of particular posets.
Given a poset P , two questions naturally arise. The generation question asks
whether the linear extensions, E(P), of P be efficiently generated. The counting
question asks whether e(P), the size of the set E(P), can be efficiently determined.
The recent result of Brightwell and Winkler [4] that the counting question is #P-
complete indicates that the counting question may be no easier than the generation
question. We give the best possible answer to the generation question in the sense
that our algorithm generates E(P) in time complexity O(e(P)) (aside from a small
amount of preprocessing).
We say that a generation algorithm runs in constant amortized time if it runs
in time O(N ), where N is the number of objects generated. In the case of linear
extensions we assume that a unit cost oracle is available that takes two poset elements
a and b and returns whether a OE b, or not. We also assume that the poset elements
Department of Computer Science, University of Toronto, Toronto, Ontario, M5S 1A4, Canada,
gara@cs.utoronto.ca. Research supported in part by NSERC. Research in this paper took place
while visiting Simon Fraser University, Burnaby, Canada.
y Department of Computer Science, University of Victoria, Victoria, B.C., V8W 2Y2, Canada,
fruskey@csr.uvic.ca. Research supported in part by the Natural Sciences and Engineering Research
Council of Canada under Grant A3379.
have been labeled in a particular manner, to be described later. This labeling can be
carried out in time O(n 2 ) on an n element poset. Aside from the space used for the
poset, the amount of space required by our algorithm is O(n). No constant amortized
time generation algorithm was previously known for a class of combinatorial objects
for which the corresponding counting problem is #P-complete.
The problem of generating the linear extensions of a poset has been considered
by Knuth and Szwarcfiter [12], Varol and Rotem [24], and Kalvin and Varol [11]. In
these papers the term "topological sorting" is used instead of "linear extension". The
most efficient of these algorithms appears to be that of Varol and Rotem [24], whose
time complexity is given as O(n \Delta e(P)) in [11], where n is the number of elements in
the poset. It is worth noting that the Varol and Rotem algorithm is very simple and
elegant, and is quite efficient in practice. The only algorithm that we are aware of for
counting linear extensions of arbitrary posets is that of Wells [25], but it appears to be
difficult to analyze. For particular classes of posets, such as series-parallel or bounded
width, efficient algorithms for counting are known (see, for example Bouchitte and
Habib [3]).
2. Strategy and Definitions. A popular strategy for efficiently generating
some set of combinatorial objects is to insist that successive objects in the listing
differ by some small and prescribed way. Listings of combinatorial objects that have
this property are called (generalized or combinatorial) Gray codes. For example, the
binary reflected Gray codes yield a method for generating all the n-bit strings such
that each bit string differs from its predecessor by the flipping of one bit. Gray
codes have been found for several classes of combinatorial objects; many of these are
described in Wilf [26].
We will regard linear extensions as permutations of the elements of the poset.
When generating various classes of permutations, the most common "closeness" criteria
is that successive permutations differ by a transposition of two of their elements;
sometimes this is further restricted to a transposition of adjacent elements only. The
well-known algorithm of Steinhaus [22], Johnson [10], and Trotter [23] provides a Gray
code listing of all the n! permutations of n elements where each permutation differs
from its predecessor by a transposition of two adjacent elements. Thus we say that
the n! permutations can be generated by (adjacent) transpositions. The permutations
of an n-set correspond to the linear extensions of the poset that is an n element
antichain.
In general, it is not always possible to generate the linear extensions of a poset
by transpositions, adjacent or not; for example, the linear extensions of the poset
consisting of two non-trivial chains and only if n and m are both odd ([5], [6], and
[16]). Thus, the linear extensions of the poset in Figure 1 (two 2-element chains)
cannot be generated by transpositions. The linear extensions of some classes of posets
have been shown to be generable by transpositions (see [18],[15], [20]). It is an open
problem to characterize the posets which have this property. Even when the linear
extensions of a family of posets can be generated by transpositions, a fast algorithm
to perform the generation may not exist.
The basic strategy of our initial algorithm is to generate each linear extension
twice, where each extension is flagged, plus or minus. The algorithm keeps track of
the signs of the extensions and only "outputs" the plus extensions. Thus, in a sense,
this algorithm falls into the class of generation algorithms that generate more objects
than those that are actually output.
We now introduce our terminology and notation.
A poset (or partially ordered set) P is a reflexive, transitive, and antisymmetric
relation R(P) on a set S(P). An ordered pair (a; b) 2 R(P) is denoted a -P b, or,
when it will not lead to confusion, simply a - b. By a OE b we mean a - b and a 6= b.
An element a is minimal in P if there is no element b such that b OE a. Let Min(P)
denote the set of minimal elements of P . If a OE b and there does not exist a c in
S(P) such that a OE c OE b, then we say that b covers a. Let Cover(a) denote the set
of elements that cover a. Elements a and b are said to be incomparable if a 6- b and
b 6- a. We write akb to indicate that a and b are incomparable. If no pair of elements
of S(P) are incomparable, then P is a total ordering. If P is a total ordering on
such that x i OE x j if and only if i ! j, then we sometimes use
xn to denote P . An extension of P is a poset Q such that
An extension of P which is a total ordering is called a linear extension
of P . Let E(P) denote the set of linear extensions of P , and let e(P) denote jE(P)j.
We let \SigmaE(P) denote f+l; \Gammal j l 2 E(P)g.
The height, h(x), of an element x is the average position that it occupies in a
linear extension. Thus, a minimum element has height 1, a maximum element has
height jS(P)j, and if P is an antichain, then all elements have height (jS(P)j
The probability that x precedes y is denoted P it is the number of extensions
in which x precedes y divided by the total number of extensions. In connection with
sorting algorithms it is desirable to find pairs of elements x and y where P
close to 1/2.
For T ' S(P), we let PnT denote the poset on the set S(P)nT with the relations
set Suppose a and b are incomparable elements of S(P) such
that a has the same relationship to all other elements of S(P) as b; more precisely,
suppose that, for all c 2 S(P), c OE a if and only if c OE b, and a OE c if and only
if b OE c. Then a and b are called siblings. For posets P and Q, if R(P) [ R(Q) is
antisymmetric, then we let P +Q denote the poset on the set S(P) [ S(Q) with the
relation set which is the transitive closure of R(P)[R(Q). For example, P+abc is the
poset on the set S(P) [ fa; b; cg with the relation set which is the transitive closure
of R(P) [ f(a; b); (b; c)g. If P then we say P induces Q. For example,
and every linear extension of P has
a OE b OE c; therefore, we say P induces abc. For element disjoint total orders ff; fi; fl; ffi,
we denote the poset fffi
Consider the graph which has E(P) as its vertex set, such that two vertices are
adjacent in the graph whenever the corresponding linear extensions differ by a single
transposition. This graph is called the transposition graph of the poset P and is
denoted G(P). The subgraph of G(P) on the same vertex set but containing only the
edges which correspond to adjacent transpositions is called the adjacent transposition
graph and is denoted G 0 (P). Generating the linear extensions of P by (adjacent)
transpositions is equivalent to finding a Hamiltonian path in the graph G(P) (G 0 (P)).

Figure

1 shows a poset and its transposition graph. If ff and fi are linear extensions
of P , then by D(ff; fi) we denote the distance in G(P) from ff to fi, and by D 0 (ff; fi)
we denote the corresponding distance in G 0 (P).
Transposition graphs are bipartite and connected. If the partite sets of G(P)
are not the same size, then there is no Hamiltonian cycle through the graph; if the
difference in the size of the partite sets is more than one, there is no Hamiltonian
path through the graph and thus, the linear extensions of P cannot be generated by
transpositions. Ruskey [17] conjectures that this necessary condition for the existence
of a Hamiltonian path is also sufficient, suggesting a possible characterization of the
@
@
@
@
@
@
s
a 1
s
a 2
s
s
s a 1 a
s
Fig. 1. A poset and its transposition graph.
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
s
s
s
s
s
s
s
s
s
s
s
s
Fig. 2. The graph G(P) \Theta K 2 .
posets whose linear extensions can be generated by transpositions. In Figure 1, the
partite sets have a size difference of two, so the linear extensions of that poset cannot
be generated by transpositions.
If G is a graph, then let G \Theta K 2 be the graph which results from taking two
copies of G, and adding the edges which correspond to an isomorphism between the
two copies. To differentiate between the copies of G, we will prefix the vertices of one
copy of G with "+" and the other with "\Gamma". For example, Figure 2 shows G(P) \Theta K 2 ,
where P is the poset shown in Figure 1.
A lemma which will be useful in later sections can be stated as follows:
Lemma 2.1. If a and b are siblings in P, then G(P)
Proof. Observe that ba). For any linear extension
l of P , transposing a and b in l yields another linear extension of P . Therefore, the
operation which transposes a and b in a linear extension provides an isomorphism
If is a total order), G(P) \Theta K 2 is an edge. For the purpose
of inductively showing the existence of Hamiltonian cycles, we consider this graph to
have a Hamiltonian cycle, since it has a Hamiltonian path such that the endpoints
are adjacent.
3. The Graph G 0 (P) \Theta K 2 is Hamiltonian. The proof that G 0 (P) \Theta K 2 is
Hamiltonian forms the basis of the efficient algorithm to be presented in the next
section. That this is true for a certain kind of poset, called a B-poset, was shown by
@
@
@
y 9
r
r
r
r
r
r
r
r
r
r
r
r
Fig. 3. A B-poset.
Pruesse and Ruskey [15], and this result will be used in the proof of the general case.
Definition 3.1. A B-poset is a poset P whose elements can be partitioned into
two disjoint chains, x 1 OE x
for all i and j, where 1
An example of a B-poset is shown in Figure 3. Note that
is a linear extension of any B-poset. The extension - is called the canonical linear
extension of a B-poset. Define mr(x i ) to be the largest index j such that x i k y
For the B-poset of Figure 3, 7.
The following lemma was proved in [15].
Lemma 3.2. Let P be a B-poset. Then there exists a Hamiltonian cycle in
uses the edge [+-; \Gamma-].

Figure

4 shows the graph G 0 (P) \Theta K 2 , where P is the B-poset shown in Figure 3.
The edges corresponding to the isomorphism between the two copies of G 0 (P) have
been omitted for the sake of clarity. One can think of traveling up a vertical edge as
transposing its neighbor on the right, and traveling along a horizontal
edge as transposing a = x 1 with one of its neighbors. A Hamiltonian path between
+- and \Gamma- is shown in Figure 5. All B-posets used in the remainder of the paper
have we call these 2B-posets.
A graph similar to that shown in Figure 4 arises whenever we call this the
typical case. If a OE y 1 then G 0 (P) is a path; we call this the atypical case. In other
words, the typical case occurs when mr(a) ? 0 and the atypical case occurs when
Theorem 3.3. For every poset P, the graph G 0 (P) \Theta K 2 is Hamiltonian.
Proof. The proof of the theorem is by induction on jS(P)j. For the base cases of
the induction, P is the poset on zero or one elements; in both of these cases G 0 (P) \Theta K 2
is an edge.
Suppose jS(P)j ? 1. If P has a unique minimum a, then G 0 (P)
and by the inductive hypothesis G 0 (Pnfag) \Theta K 2 is Hamiltonian.
Otherwise, let P have two minimal elements a and b. By the inductive hypothesis,
the graph G 0 (Pnfa; bg) \Theta K 2 has a Hamiltonian cycle H 0 . Replace each signed linear
extension +ff i on H 0 with abff replace each linear extension \Gammaff i with baff i . The
result is a cycle
exactly those linear extensions in which a and b precede all other elements of S(P).
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
\Gammaay
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
Fig. 4. The graph G 0 (P) \Theta K2 .
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
Fig. 5. A Hamiltonian cycle through G 0 (P) \Theta K 2 .
That is, this cycle visits all the linear extensions of
x2S(P)nfa;bg
The poset P 0 is P extended so that a and b are covered by every other element of
Min(P).
For each fi a, the poset P+x i y
is a B-poset. By Lemma 3.2, there is a Hamiltonian path through G 0 (P+x
from +fi i to \Gammafi i . We substitute the occurrence of fi i with this path in H 0 , for each
odd i. For each even i, we substitute the reverse of this path for the occurrence of fi i .
Call the resulting walk H .
To prove that H is a Hamiltonian cycle through G 0 (P) \Theta K 2 , it is necessary
to show that every vertex on the cycle H is a linear extension of P ; this is true,
since E(P 0 ) ' E(P), and hence each B-poset generated is an extension of P . It is
also necessary to show that for each linear extension l of P , +l and \Gammal both occur
exactly once on H . Suppose l induces the order xy on fa; bg and the order i on
bg. Then xyi is a linear extension of P 0 , and l is a linear extension of the
B-poset every other B-poset generated either does not induce the
order xy or does not induce the order i. Therefore, +l and \Gammal are generated only
during the generation of E(P each +l and \Gammal are generated exactly
once.
Observe that the reference to Lemma 3.2 in the preceding proof was not strictly
necessary because the B-posets that occur are all 2B-posets. In the "typical" case,
the cycle of Figure 5 could be used; in the "atypical" case the cycle is obvious (move b
to the right as far as possible, change signs, and then move the b back to the left). If
mr(b) is even, the cycle of Figure 5 is slightly different and uses the edge [+aflb; \Gammaaflb],
These cycles are used in the algorithm of the following section.
Corollary 3.4. If P is a poset with a pair of siblings, then G(P) is Hamiltonian

Proof. Suppose P has a pair of siblings a; b. By Theorem 3.3, G
Hamiltonian; therefore G(P Hamiltonian. Hence by Lemma 2.1, G(P)
is Hamiltonian.
It is an open problem to determine whether G 0 (P) is Hamiltonian, where P is a
poset with a pair of siblings.
4. The Algorithm. The proof of Theorem 3.3 is constructive. In this section,
we present the recursive algorithm implicit in the inductive proof. The algorithm runs
in constant amortized time; i.e., generating all the linear extensions of a poset P takes
time O(e(P)).
We first give an overview of the algorithm and use a small example to give a
general understanding of how it works. We then give the details of the algorithm and
a proof of its correctness.
The algorithm is an in-place algorithm; it maintains an array le in which contains
the current linear extension, and maintains a variable IsPlus which keeps track of the
sign ("+" or "\Gamma"). We go from one linear extension to the next by making changes
to the array or reversing the sign.
The main procedure used by the algorithm, which we call GenLE, is recursive and
basically follows the path indicated in Figure 5. Every level of the recursion has an
associated pair of minimal elements of the current subposet. For example, in the
poset shown in Figure 1, a are a pair of minimal elements of
are a pair of minimal elements of g. These pairs are determined by
some preprocessing which will be described later.
The procedures Move and Switch are used to change the current linear extension.
They operate in O(1) time as follows:
then the sign is changed; that is, IsPlus is changed. If
are transposed.
This call transposes x with the element on its left.
This call transposes x with the element on its right.
Each time a new linear extension l of P i is generated by the call GenLE(i) (i.e.,
each time Move or Switch is called), GenLE(i-1) is called; the call GenLE(i-1) moves
in all possible ways through l, while maintaining the order a
depending on their order at the point of calling GenLE(i-1)).
does nothing.
For example, starting with +a 1 b 1 a 2 b 2 and executing the calling sequence GenLE(2),
Switch(2), GenLE(2) on the poset shown in Figure 1 leads to the trace of calls shown
in

Figure

6.
We now follow with the details of our implementation. The reader should refer
to the Pascal procedure GenLE of Figure 8.
The implementation of the algorithm maintains four global arrays: array le is
the linear extension; array li is its inverse. Arrays a and b store the elements a i
and b i . In our discussion of the algorithm, a i and b i are considered to be fixed at
the outset and unchanging throughout the run of the algorithm. The arrays will be
maintained so that a[i] always contains the value of the leftmost of the ith pair, and
Procedure Call Linear Extension
Fig. 6. The trace of the calling sequence for the poset of Figure 1.
b[i] contains the rightmost. Also, the current sign, either plus (+) or minus (\Gamma), is
maintained.
The boolean function Right(x) is used to determine whether the element x can
move to the right. It operates in O(1) time as follows:
Returns true only if b[i] is incomparable with the element to its
right in the array le.
Returns true only if a[i] is incomparable with the element to its
right in the array le and the element to the right is not b[i].
We now describe our preprocessing. We successively strip off pairs a
elements there are no elements left. If a unique minimum
element is encountered then it is simply deleted and does not become part of a pair.
Let MaxPair be the index of last pair of minimal elements we strip from P , the remainder
of P being a total ordering, or empty. This preprocessing is detailed in Figure
7. Note that MaxPair is not uniquely determined by the poset, but that it depends
on the order in which the elements are stripped from P .
We say the linear extension l is in proper order up to i if for all 1
the elements a j and b j are adjacent in l, and l induces the orders a 1 a
a 1 a MaxPair. The initial linear extension of the
listing must be properly ordered up to MaxPair; the preprocessing of Figure 7 does
this.
Assuming that Right( b[MaxPair+1] ) is false, the initial call is simply GenLE(
this is the same as the following procedure calls, which we call the
calling sequence.
GenLE( MaxPair ); Switch( MaxPair ); GenLE( MaxPair );
The algorithm consists of executing the preprocessing, setting IsPlus to plus (+),
while S(Q) 6= ; do
if Q has exactly one minimal element x then begin
else begin
let a be any two minimal elements of Q;
a[i] / a
MaxPair /
Fig. 7. The preprocessing routine.
and then executing the calling sequence.
A Pascal procedure implementing GenLE is given in Figure 8. We now prove the
following theorem.
Theorem 4.1. The algorithm GenLE generates the linear extensions along a
Hamiltonian path in G 0 (P) \Theta K 2 .
Proof. In order to prove the theorem, we first prove the following proposition.
Proposition 4.2. Let the linear extension in array le be
- be properly ordered up to i. Then for each linear extension l 2 E(P
GenLE(i) generates each of +l, \Gammal exactly once. Furthermore, if then the last
extension generated is \Gamma-, and if i ? 1 then the last extension generated is +- 0 , where
differs from - by a transposition of a i\Gamma1 and b i\Gamma1 .
Proof. The proof proceeds by induction on i. If recursive calls GenLE(0)
do nothing, Switch(0) just changes the sign, and ffia 1 is induced by P .
It is easy to confirm that the algorithm in Figure 8, when stripped of its recursive
calls, and in which Switch just changes the sign, simply follows the path indicated
in

Figure

2. In this case, GenLE(1) just finds a Hamiltonian path from +- to \Gamma-
through G 0 (Q) \Theta K 2 , where Q is the 2B-poset P
loss of generality that the sign in storage when GenLE
is invoked is "+". There are ff; fi; fl such that Because of
the way the preprocessing selects the pairs a , we are assured that P induces the
could be empty).
As mentioned before, the basic structure of the algorithm, stripped of recursive
calls, follows the Hamiltonian path in a 2B-poset as indicated in Figure 2, where
Switch now transposes a
Each linear extension in +E 0 is properly ordered up to i \Gamma 1.
As each such linear extension
is called on +l. By the inductive
procedure GenLE
begin
mrb := 0; typical := false;
while Right( b[i] ) do begin
Move( b[i], riht ); GenLE( i-1 );
mra := 0;
if Right( a[i] ) then begin
typical := true;
repeat
mra
Move( a[i], riht ); GenLE( i-1 );
until not Right( a[i] );
if typical then begin
for x := 1 to mla do begin
Move( a[i], left ); GenLE( i-1 );
if typical and odd( mrb )
then Move( a[i], left )
else Switch( i-1 );
for x := 1 to mrb do begin
Move( b[i], left ); GenLE( i-1 );
Fig. 8. Pascal procedure GenLE.
hypothesis, that call generates \SigmaE(P + a
respectively), starting at +l and ending at +l 0 if i ? 2, and ending at \Gammal if 2.
Since there are an even number of vertices in the product of the graph with a edge,
there are an even number of calls to GenLE(i-1). Thus if i ? 2 then the sign of the
final permutation is unchanged, and if then the relative ordering of a i\Gamma1 and
b i\Gamma1 is unchanged. The union over all such i is \SigmaE(P +a
b
Let a; b be a[MaxPair], b[MaxPair] respectively, and suppose the calling sequence
is executed on the preprocessed poset P . By the proposition, the first call to
then a and b are transposed, and then \SigmaE(P + ba) is
generated. Therefore, E(P) is generated, and the Theorem is proved.
In analyzing the time complexity of the algorithm, we assume that Right, Switch,
and Move can be implemented in constant time. This is easily accomplished as long
as the inverse li of le is maintained. Each call to Move and Switch generates one
more linear extension. Observe that the call GenLE(i) generates at least two calls
to GenLE(i-1). Each iteration of a while-loop or for-loop in the algorithm executes
a Move, thereby generating a linear extension. The only occasion in which GenLE
can be recursively called and no linear extension generated is when
happens at most once per linear extension generated. Therefore, the algorithm runs
in constant time per linear extension, when generating \SigmaE(P). By suppressing the
linear extensions which are prefixed with "\Gamma", we generate E(P) in constant amortized
time. Another way to think of the preceding argument is to consider the underlying
computation tree, where each internal node is a recursive call and each leaf is a linear
extension. The total amount of computation can be divided up so that each node
is assigned a constant amount of computation. Since each internal node has at least
two children, the number of leaves is greater than the number of internal nodes and
therefore the total amount of computation is proportional to the number of leaves.
Observe that the generation of the minus ("\Gamma") vertices only occurs when
Algorithm GenLE. This suggests that treated as a special case and that minus
("\Gamma") vertices be omitted entirely by simply skipping to the next plus ("+") vertex. If
this is done, then it saves some computation but the same list of extensions is produced
as before, and successive extensions can differ by a large number of transpositions.
If one only wants to compute the number of extensions, then some computation
can be saved by only computing the number of vertices at the level of the
recursion, and not generating the extensions explicitly; i.e., never moving a 1 and
. The number of vertices (extensions) can be determined from mr(a) = mra and
the number is (mr(a)
and mr(b) change by at most unity from one extension to the next, since only adjacent
transpositions are used. This leads to an algorithm whose running time is O(e(P n
In general, we have
The lower bound is attained when a 1 OE c and b 1 OE c for all elements c of P n g.
The upper bound is attained when a 1 and b 1 are maximal, as well as minimal.
5. Gray Codes for Linear Extensions. We now show that linear extensions
can be listed so that successive extensions differ by at most a few adjacent transposi-
tions. We first show the existence of such listings, and then how to modify the results
of the previous sections to show that the set of linear extensions of a poset can be
listed so that successive extensions differ by only one or two adjacent transpositions.
Let us say that an ordering ff of the extensions of P has delay C if
. Thus we are going to show
the existence of a delay 2 ordering of E(P). Furthermore, such a listing can be done
in constant amortized time. The existence of a delay 3 ordering is not difficult to
show.
If G is a graph then by G k we denote the graph with the same vertex set as G
but which has an edge between every pair of vertices that are connected by a path of
length at most k in G. In other words, if M is the incidence matrix of G, then M k
is the incidence matrix of G k , where arithmetic is done mod 2. The cube of G is G 3
and the square of G is G 2 . A poset P has a delay k ordering if and only if G 0 (P) k is
Hamiltonian. A result of Sekanina [19] is that the cube of every connected graph is
Hamiltonian. Since G 0 (P) is always connected, G 0 (P) 3 is Hamiltonian and a delay 3
ordering exists.
The graph G 0 (P) is not always 2-connected; otherwise the existence of a delay 2
ordering would by implied by a result of Fleischner [7] which states that the square
of every 2-connected graph is Hamiltonian.
Even though G 0 (P) is not in general 2-connected, the posets with 2-connected
transposition graphs are easy to characterize. First, consider the question of which
transposition graphs have pendant vertices. If P consists of two disjoint chains, then
G 0 (P) has two pendant vertices; if P is a B-poset and is not the disjoint union of two
chains, then G 0 (P) has one pendant vertex; otherwise G 0 (P) has no pendant vertices.
Lemma 5.1. For every poset P, the graph H(P) is 2-connected, where H(P) is
pendant vertices.
This may be proven by showing that every pair of incident edges of H(P) is on
a 4, 6, or 8-cycle. This lemma does not help us in finding an efficient algorithm for
listing a delay 2 ordering of E(P). Instead, we prove it by applying Theorem 3.3 and
the following lemma.
Lemma 5.2. If G is bipartite and G \Theta K 2 is Hamiltonian, then G 2 is Hamiltonian.
Proof. Let G be a bipartite graph on n vertices, and let
be a Hamiltonian cycle through G \Theta K 2 , where v
for all Consider the sequence of vertices
Since G is bipartite, so is G \Theta K 2 ; thus the vertices of S are all the vertices of
one partite set of G \Theta K 2 . Also, for a vertex u of G, (u; 1) and (u; 2) are adjacent are
are therefore in different partite sets of G \Theta K 2 . Therefore each vertex of G appears
exactly once in S. For each i, the vertices v i and v i+2 are either of distance one in G
or of distance two in G (if x Therefore S is a Hamiltonian
cycle in G 2 .
We conjecture that Lemma 5.2 may be extended to graphs which are not bipartite.
Conjecture 5.3. If G \Theta K 2 is Hamiltonian, then G 2 is Hamiltonian.
A graph is in class H(s; t) if it has a closed walk that visits every vertex at least
s times and at most t times. (See [8], [14].) Thus H(1; 1) is the class of Hamiltonian
graphs. Observe that if G \Theta K 2 is Hamiltonian, then G 2 H(1; 2) (just consider the
walk that results when the two copies of G are identified). The converse is not true;
if G is the triangle with a pendant edge added to each vertex, then G 2 H(1; 2)
but G \Theta K 2 is not Hamiltonian. Theorem 3.3 shows that for every poset P , the
graph G 0 (P) is in H(1; 2). In general, these graphs are not Hamiltonian. We make a
conjecture.
Conjecture 5.4. If G 2 H(1; 2), then G 2 is Hamiltonian.
The example of K 2;6 shows that the converse of the conjecture is false.
The proof of Lemma 5.2 is constructive; applying that construction to G 0 (P)
yeilds the following result.
Theorem 5.5. The linear extensions of any poset can be generated with delay 2
in constant amortized time.
Proof. We run the Algorithm Genle given in Figure 8, but instead of suppressing
the linear extensions with a negative sign, we suppress every other linear extension;
i.e., if we generate the list l 1 then we output the list l 1
the proof of Lemma 5.2, this is a delay 2 listing of the linear extensions. It has the
same running time as Genle, i.e., constant amortized time.
In the remainder of this section we discuss how to use the algorithm to compute
We use the version of GenLE that generates each extension exactly
twice, where each successive extension differs by an adjacent transposition from its
predecessor. We first discuss how to compute P
Let us define an xy-run to be a maximal sequence of successive extensions where
x precedes y. We maintain two arrays of integers, call them S and T . The value
of S[x; y] is the sum of the lengths of the previous xy-runs. The value of T [x; y]
is the iteration at which the current xy-run started. At each iteration, exactly one
adjacent pair, say xy, is transposed. If this occurs at the t-th iteration, then S[x; y] is
incremented by t \Gamma T [x; y] and T [y; x] is set to t. At the termination of the algorithm,
divided by 2e(P). Since only a constant amount of update is done
at each iteration the total computation is O(n
To compute h(x) we proceed in a similar fashion. An x-run is a maximal sequence
of extensions in which x occupies the same position. Here the value of S[x] is the
weighted sum of the lengths of the previous x-runs and T [x] is the iteration at which
the current x-run started. At each iteration exactly one adjacent pair, say xy, is
transposed. If this occurs at the t-th iteration, then for y, S[z] is incremented
by p[z]   set to t, where p[z] is the position that z occupied in
the extension. At termination the value of h(x) is S[x] divided by 2e(P).
6. Concluding Remarks. The algorithm given in section 6 generates the linear
extensions of a poset in constant amortized time, an improvement over the O(n)
amortized time algorithm of [11], which is the fastest previously known algorithm.
A further refinement to the work presented here would be to generate the linear
extensions by a "loopfree" algorithm (i.e., constant computation in the worst case in
producing a new extension from the current one).
We have fully implemented the counting and generating algorithms in C and
found them to be quite efficient in practice. On a Sun SPARCstation SLC, the
program generated the 2,702,765 extensions of a 12 element fence poset in 4.2 seconds.
These extensions are counted by the Euler numbers; counting took 1.7 seconds. The
199,360,981 extensions of a 14 element fence were counted in 91 seconds and generated
in 281 seconds. The 2,674,440 extensions of the 2 by 14 grid were generated in 8.3
seconds. These extensions are counted by the Catalan numbers.
Enumeration of the linear extensions of a poset has recently been shown to be
#P-complete. The algorithm in section 3 constitutes the first constant amortized time
algorithm for generating a naturally defined class of combinatorial objects where the
associated counting problem is #P-complete. This leads to some interesting questions
about the complexity of generating other combinatorial objects for which counting is
#P-complete.
Do all #P-complete problems admit constant amortized time generation algo-
rithms? In asking this question we assume that an initial object has been supplied as
part of the input. For example, for Hamiltonian cycles the input would consist of a
graph G and a Hamiltonian cycle in G; similarly, in this paper we have assumed that
is a linear extension of the input poset.
Intuitively, if the existence question is difficult (NP-complete), then the generation
question will be difficult as well, but we have not answered, or even formalized, this
intuition. Even if the existence question is easy (in P), there are many problems for
which the complexity of generating is unknown. For example, can the ideals of a given
input poset be generated in constant amortized time? Counting ideals is #P-complete,
but finding an ideal is trivial. What about generating the spanning trees of a graph in
constant amortized time? Finding a spanning tree and counting the number of such
trees are both in P, but no one has discovered a constant amortized time algorithm for
generating the spanning trees. Is there, in fact, any interesting relationship between
constant amortized time generation algorithms and the complexity of existence and/or
counting? Some related questions, for various polynomial time complexity measures
(instead of constant amortized time), were considered by Johnson, Yannakakis, and
Papadimitriou [9].

Acknowledgements

. We would like to thank Derek Corneil, Mike Fellows,
and Carla Savage for helpful discussions, Malcolm Smith for work on the figures,
and especially Ken Wong for implementing the algorithms and carefully reading the
manuscript.
Note added in proof. As was pointed out by L. Babai (private communication),
it is easy to contrive a #P-complete object that can be generated quickly by starting
with a #P-complete object, and pumping up the number of instances by taking the
union with an easily-counted, easily-generated, but more numerous object. For exam-
ple, given a poset P on n vertices, consider the set fx : x is an ideal of Pg[ fx : x '
]g. This set is #P-complete to count and, given an appropriate representation, is
easy to generate in constant amortized time.
A counterexample on twenty-four vertices to conjectures 5.3 and 5.4 has recently
been found by J. van den Heuvel (private communication).



--R

Webster's New Collegiate Dictionary
Combinatorial Theory
The calculation of invariants for ordered sets
Counting linear extensions is
Gray codes with restricted density
Some Hamilton paths and a minimal change algorithm
The square of every two-connected graph is Hamiltonian

On generating all maximal independent sets
Generation of permutations by adjacent transpositions
On the generation of all topological sortings
A structured program to generate all topological sorting ar- rangements
Complexity of machine scheduling problems
A generalization of hamiltonicity
Generating the linear extensions of certain posets by transposi- tions
Adjacent interchange generation of combinations


On an ordering of the set of vertices of a connected graph
Hamilton paths in graphs of linear extensions for unions of posets

One Hundred Problems in Elementary Mathematics
Algorithm 115: Perm
An algorithm to generate all topological sorting arrangements
The elements of combinatorial computing
Combinatorial Algorithms
--TR

--CTR
Scott Effler , Frank Ruskey, A CAT algorithm for generating permutations with a fixed number of inversions, Information Processing Letters, v.86 n.2, p.107-112,
Jean-Luc Baril , Vincent Vajnovszki, Minimal change list for Lucas strings and some graph theoretic consequences, Theoretical Computer Science, v.346 n.2, p.189-199, 28 November 2005
J. Sawada, Oracles for vertex elimination orderings, Theoretical Computer Science, v.341 n.1, p.73-90, 5 September 2005
L. S. Chandran , L. Ibarra , F. Ruskey , J. Sawada, Generating and characterizing the perfect elimination orderings of a chordal graph, Theoretical Computer Science, v.307 n.2, p.303-317, 7 October
Karel De Loof , Hans De Meyer , Bernard De Baets, Exploiting the Lattice of Ideals Representation of a Poset, Fundamenta Informaticae, v.71 n.2,3, p.309-321, August 2006
Gang Wang , Wenrui Gong , Ryan Kastner, Instruction scheduling using MAX-MIN ant system optimization, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
Russ Bubley , Martin Dyer, Faster random generation of linear extensions, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.350-354, January 25-27, 1998, San Francisco, California, United States
Karell Bertet , Jens Gustedt , Michel Morvan, Weak-order extensions of an order, Theoretical Computer Science, v.304 n.1-3, p.249-268, 28 July
Larry Huston , Rahul Sukthankar , Rajiv Wickremesinghe , M. Satyanarayanan , Gregory R. Ganger , Erik Riedel , Anastassia Ailamaki, Diamond: A Storage Architecture for Early Discard in Interactive Search, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
Martin Charles Golumbic , Ron Shamir, Complexity and algorithms for reasoning about time: a graph-theoretic approach, Journal of the ACM (JACM), v.40 n.5, p.1108-1133, Nov. 1993
transposition;poset;combinatorial Gray code;linear extension