linearExtensions -- computes all linear extensions of a poset

Synopsis

Usage:

L = linearExtensions P
Inputs:
- P, an instance of the type Poset,
Outputs:
- L, a list, all possible linear extensions of $P$

Description

A linear extension of the partial order on $P$ is a total order on the elements of $P$ that is compatible with the partial order.

i1 : P = divisorPoset 12;

i2 : L = linearExtensions P

o2 = {{1, 2, 3, 6, 4, 12}, {1, 2, 3, 4, 6, 12}, {1, 2, 4, 3, 6, 12}, {1, 3,
     ------------------------------------------------------------------------
     2, 6, 4, 12}, {1, 3, 2, 4, 6, 12}}

o2 : List

The flatten of the filtration of $P$ is always a linear extension. This approach is much faster, especially for posets with many linear extensions.

i3 : F = flatten filtration P

o3 = {1, 2, 3, 4, 6, 12}

o3 : List

i4 : member(F, L)

o4 = true

The partial order of a chain is the total order of the elements.

i5 : linearExtensions chain 10

o5 = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}

o5 : List

This method was ported from John Stembridge's Maple package available at http://www.math.lsa.umich.edu/~jrs/maple.html#posets.

Ways to use linearExtensions :

linearExtensions(Poset)

For the programmer

The object linearExtensions is a method function.

linearExtensions -- computes all linear extensions of a poset

Synopsis

Description

See also

Ways to use linearExtensions :

For the programmer