#14126: Count Number of Linear Extensions of a Poset
-------------------------------------+-------------------------------------
Reporter: csar | Owner: sage-combinat
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: days45 | Merged in:
Authors: aschilling, | Reviewers:
nthiery, hivert | Work issues:
Report Upstream: N/A | Commit:
Branch: u/jmantysalo | f908696aa7c63cefbc382af326cfe085e0dfa522
/count-lin-ext | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by jmantysalo):
I just tested how much we could save by just mechanically copying the
code.
After `P6 = Posets(6).list()` it took 0.45 seconds to compute
`sum([len(P.linear_extensions().list()) for P in P6])`, and 0.11 second to
`sum([P.linear_extensions().count() for P in P6])`. For 14-element
`Posets.TamariLattice(4)` it took 1.42 seconds to compute list of linear
extensions and 0.24 seconds to just count them. Is this speedup useful?
For general posets we could split it to connected components first. For
lattices we could check if it is vertically decomposable. But is there
some other ways to speed up this? Maybe somehow find chains of doubly
irreducible elements?
--
Ticket URL: <http://trac.sagemath.org/ticket/14126#comment:21>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
