#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: Jori Mäntysalo | Reviewers:
Report Upstream: N/A | Work issues:
Branch: u/jmantysalo | Commit:
/count-lin-ext | f908696aa7c63cefbc382af326cfe085e0dfa522
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by kdilks):
The {{{#P}}} result you keep citing only applies to generating a list all
linear extensions, not counting them. For example, I can tell you that the
number of linear extensions of an antichain of size n is n!, independent
of any complexity issues that arise when trying to generate all n!
permutations.
The algorithm is used in Stembridge's Posets package. The general idea is
that linear extensions are maximal chains in the lattice of order ideals.
If you want to enumerate (not generate) maximal chains, then you can use
fact that if f(x) is the number of saturated chains from a minimal element
to x, then f(y) = sum f(x) over all x covered by y.
If we wanted to keep the code simple, we could just create the lattice of
order ideals {{{J(P)}}} using Sage. But then the elements of this poset
would be subsets, and we'd have another (potentially expensive)
computation to make the Hasse diagram and get a naturally labelled poset
on {{{0...(|I|-1)}}} (where {{{|I|}}} is the number of order ideals). I
think I tried this implementation in the past, and it was still an order
of magnitude or two slower than the corresponding Maple code.
However, there should be some wizardry that lets us quickly create a
dictionary on {{{0 .. (|I|-1)}}} corresponding to the up edges in
{{{J(P)}}}. That wizardry is what I'm trying to figure out.
This algorithm works whether or not P is connected. However, there would
be some significant speed-up for posets with a large number of connected
components if we just counted the number of linear extensions on each
connected component, and combined the results appropriately (if f(P) is
the number of linear extensions on P, and P=P_1 U ... U P_k , then f(P)=
multinomial(|P|,{|P_1|,...,|P_k|}) * product f(P_i) .
For example, say we look at the anti-chain of 11 elements. Currently, we
have to iterate over close to 40 million permutations. Using the wizardry,
we would just have to create a dictionary of 2048 elements corresponding
to up-edges in the Boolean lattice and iterate over it. And if we split
into connected components...getting 11! is almost automatic.
--
Ticket URL: <https://trac.sagemath.org/ticket/14126#comment:31>
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 https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
