Fast linear extension iterator

sage.combinat.posets.linear_extension_iterator.linear_extension_iterator(D)[source]

Iterate over the linear extensions of the poset.

The list _le keeps track of the current linear extensions. The boolean variable is_plus keeps track of the “sign”.

INPUT:

  • D – the Hasse diagram of a poset

Warning

It is assumed that D is not modified while the linear extensions are generated.

EXAMPLES:

sage: from sage.combinat.posets.linear_extension_iterator import linear_extension_iterator
sage: D = Poset({ 0:[1,2], 1:[3], 2:[3,4] })._hasse_diagram
sage: list(linear_extension_iterator(D))                                        # needs sage.modules
[[0, 1, 2, 3, 4],
 [0, 2, 1, 3, 4],
 [0, 2, 1, 4, 3],
 [0, 2, 4, 1, 3],
 [0, 1, 2, 4, 3]]

sage: D = posets.BooleanLattice(3)._hasse_diagram
sage: len(list(linear_extension_iterator(D)))                                   # needs sage.modules
48

sage: D = posets.AntichainPoset(9)._hasse_diagram
sage: len(list(linear_extension_iterator(D))) == factorial(9)   # long time, needs sage.modules
True

>>> from sage.all import *
>>> from sage.combinat.posets.linear_extension_iterator import linear_extension_iterator
>>> D = Poset({ Integer(0):[Integer(1),Integer(2)], Integer(1):[Integer(3)], Integer(2):[Integer(3),Integer(4)] })._hasse_diagram
>>> list(linear_extension_iterator(D))                                        # needs sage.modules
[[0, 1, 2, 3, 4],
 [0, 2, 1, 3, 4],
 [0, 2, 1, 4, 3],
 [0, 2, 4, 1, 3],
 [0, 1, 2, 4, 3]]

>>> D = posets.BooleanLattice(Integer(3))._hasse_diagram
>>> len(list(linear_extension_iterator(D)))                                   # needs sage.modules
48

>>> D = posets.AntichainPoset(Integer(9))._hasse_diagram
>>> len(list(linear_extension_iterator(D))) == factorial(Integer(9))   # long time, needs sage.modules
True