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