[Information Index] [Generation Index] [COS homepage]

Information on Linear Extensions

A partially ordered set P = (<,S) is a reflexive, transitive relation on a set S. Another name for partially ordered set is poset. In the Object Server we assume that the set S consists of [n] = {1,2,...,n}, the first n integers. A linear extension of P is a permutation p1 p2···pn such that i < j implies that pi < pj.

[covers=1<2&3<4] On the left we show the Hasse diagram of a 4 elements poset. According to the definition, its linear extensions consist of those permutations of {1,2,3,4} that have 1 to the left of 2, and 3 to the left of 4. Thus, its 6 linear extensions are 1234, 1324, 1342, 3124, 3142, 3412. If Gray code output is requested, then each extension differs from its predecessor by one or two adjacent transpositions. In general, there is no listing in which successive extensions differ by a single transposition (adjacent or not).

The algorithm used to generate extensions in "lex" order is from the paper Y.Varol and D.Rotem, "An algorithm to generate all topological sorting arrangements", The Computer Journal, 24 (1981) 83-84. We use a recursive implementation as explained in the book F. Ruskey, Combinatorial Generation, manuscript, 1995. If Gray code output is requested, then the algorithm used is from the paper: G. Pruesse and F. Ruskey, " Generating Linear Extensions Fast", SIAM J. Computing, 23 (1994) 373-386.

Computing the number of extensions

It is a #P-complete problem to count the number of linear extensions. See G.Brightwell and P.Winkler, "Counting Linear Extensions", Order, 8 (1991) 225-242. The program used by COS computes the number of extensions in an exhaustive manner with a few shortcuts. If the width of the poset is small then a dynamic programming approach can be used to quickly compute the number of extensions.

Computing Prob(x<y)

It is often useful to compute Prob(x<y), the probability that x appears to the left of y in a randomly chosen linear extension. In COS we compute a table whose (x,y) entry is the number of extensions in which x precedes y; to obtain Prob(x<y) divide by the number of extensions. For the poset shown above the table is shown below.

x = 1234
y = 1 0 635
2 0 0 13
3 35 0 6
4 130 0

COS also outputs a pair (x,y) for which Prob(x<y) is as close to 1/2 as possible, the table entry for that pair, and the total number of extensions.

Extensions of Special Posets

Many combinatorial objects may be regarded as linear extensions of specific posets. Thus a linear extension generator may be used to output those objects. Furthermore, if the Gray code version of the extension generator is used, then the corresponding objects output often satisfy a natural closeness condition.

Combinations and permutations of a multiset

If the poset consists of disjoint chains, then the linear extensions correspond to permustions of a multiset.

Binary Trees and standard Young tableau

If the poset consists of a 2 by n grid, titled by 45 degrees, then the extensions correspond to well-formed parentheses strings (i.e., binary trees).

Set partitions with given block sizes

Programs available:
[Information Index] [Generation Index] [COS homepage]
Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 3267 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.