#14126: Count Number of Linear Extensions of a Poset
-----------------------------------------------+----------------------------
Reporter: csar | Owner: sage-combinat
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.8
Component: combinatorics | Resolution:
Keywords: days45 | Work issues:
Report Upstream: N/A | Reviewers:
Authors: aschilling, nthiery, hivert | Merged in:
Dependencies: | Stopgaps:
-----------------------------------------------+----------------------------
Comment (by kdilks):
We originally made this function not aware that linear extensions had an
iterator which would compute P.linear_extensions().cardinality() without
computing all of P.linear_extensions().
In it's current form, I believe this code iterates over all linear
extensions roughly same way the iterator does. So they should be
approximately the same speed, and if this code is better, then those
changes should be applied directly to the iterator.
However, Stembridge's posets package is still much faster at counting
linear extensions. He iterates over all linear extensions approximately
the same way we do, but when you just want a count of linear extensions,
he has separate code that counts maximal chains in J(P). There's a fast
way to count chains that doesn't involve iterating over all of them. One
might think computing J(P) is expensive, but one only needs to know the
covering relations, and we could come up with a faster implementation than
P.order_ideals_lattice() for this purpose (that method computes a poset
whose elements are sets of elements in P, and we should be able to more
quickly make an isomorphic poset on [1..n]).
I think it's worth keeping this ticket open for development of this
alternate way of counting linear extensions. Once we have a satisfactory
implementation, we can change P.linear_extensions().cardinality() to call
this special code for enumeration, rather than using the linear_extensions
iterator.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14126#comment:7>
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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
