#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 kdilks):
I just need to sit down and spend some time re-figuring out exactly how
the algorithm works (I had it coded a while ago, I thought, but lost it).
Maybe this weekend.
The idea behind counting maximal chains without enumerating them is you
have some function f on elements of your poset which gives 'number of
maximal chains with x as its maximal element'. Initialize it to be 1 on
minimal elements, you can recursively compute f(x) = sum_{y covered by x}
f(y), and then sum up f(x) on maximal elements.
With linear extensions, you think of them as being maximal chains in the
lattice of order ideals. I forget exactly how the voodoo works, but
there's some way that you can use the fact that covering relations in the
lattice of order ideals arise from covering relations in the original
poset, and iterate over a table of covering relations in your original
poset without computing the full lattice of order ideals.
This would be many many orders of magnitude faster. I don't have access to
Maple anymore to get timings with Stembridge's code, but I know it has no
problems counting number of linear extensions of things like a product of
3 chains of length 4 (64 elements) in a fraction of a second. Using the
code in this ticket, computing number of linear extensions of [2]x[3]x[3]
with just 18 elements has been running for a few minutes.
--
Ticket URL: <http://trac.sagemath.org/ticket/14126#comment:22>
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.
