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.

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.

x = | 1 | 2 | 3 | 4 |
---|---|---|---|---|

y = 1
| 0 | 6 | 3 | 5 |

2 | 0 | 0 | 1 | 3 |

3 | 3 | 5 | 0 | 6 |

4 | 1 | 3 | 0 | 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.

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.

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

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).

Programs available:

- Pseudo-lexicographic order C program
- Pseudo-lexicographic order Pascal program
- Gray code order C program
- Gray code order Pascal program

(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.

[Error Opening Counter File -- Click for more info]

©Frank Ruskey, 1995-2003.