Sage: Ticket #14126: Count Number of Linear Extensions of a Poset
https://trac.sagemath.org/ticket/14126
<p>
Posets appear to have no mechanism to count the number of linear extensions other than computing all the linear extensions and finding the length of that list. Using recursion, one can count the number of linear extensions without having to generate all the linear extensions.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14126
Trac 1.1.6csarFri, 15 Feb 2013 00:08:16 GMTstatus changed
https://trac.sagemath.org/ticket/14126#comment:1
https://trac.sagemath.org/ticket/14126#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketcsarFri, 15 Feb 2013 02:24:27 GMTstatus changed
https://trac.sagemath.org/ticket/14126#comment:2
https://trac.sagemath.org/ticket/14126#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketcsarFri, 15 Feb 2013 02:25:52 GMT
https://trac.sagemath.org/ticket/14126#comment:3
https://trac.sagemath.org/ticket/14126#comment:3
<p>
Patch does not apply and it's not clear why.
</p>
TicketncohenFri, 15 Feb 2013 09:26:00 GMTauthor set
https://trac.sagemath.org/ticket/14126#comment:4
https://trac.sagemath.org/ticket/14126#comment:4
<ul>
<li><strong>author</strong>
set to <em>aschilling, nthiery, hivert</em>
</li>
</ul>
<p>
(this code should probably be stored in <code>from sage.combinat.posets.linear_extensions</code>. Besides, your code may be faster for small cases but can also require an exponential memory, which can be a problem too).
</p>
TicketcsarFri, 15 Feb 2013 17:41:22 GMTattachment set
https://trac.sagemath.org/ticket/14126
https://trac.sagemath.org/ticket/14126
<ul>
<li><strong>attachment</strong>
set to <em>trac_14126-count_linear_extensions_of_a_poset-csar.patch</em>
</li>
</ul>
TicketcsarFri, 15 Feb 2013 17:46:29 GMT
https://trac.sagemath.org/ticket/14126#comment:5
https://trac.sagemath.org/ticket/14126#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14126#comment:4" title="Comment 4">ncohen</a>:
</p>
<blockquote class="citation">
<p>
(this code should probably be stored in <code>from sage.combinat.posets.linear_extensions</code>. Besides, your code may be faster for small cases but can also require an exponential memory, which can be a problem too).
</p>
</blockquote>
<p>
I've moved the code to <code>sage.categories.finite_poset</code>, which I realise is not what you've said, and added a note in the docstring saying one may prefer to count linear extensions of <code>P</code> by using <code>P.linear_extensions().cardinality()</code>, which uses the iterator belonging to <code>LinearExtensionsOfPoset</code> and avoids all the cacheing.
</p>
TicketncohenFri, 15 Feb 2013 18:25:58 GMT
https://trac.sagemath.org/ticket/14126#comment:6
https://trac.sagemath.org/ticket/14126#comment:6
<p>
<code>O_o</code>
</p>
<p>
Well, shouldn't the two codes that compute the number of linear extensions be at the same place ?... A choice could be madebetween the two with an argument to <code>cardinality()</code>.
</p>
<p>
Nathann
</p>
TicketkdilksFri, 15 Feb 2013 20:46:02 GMT
https://trac.sagemath.org/ticket/14126#comment:7
https://trac.sagemath.org/ticket/14126#comment:7
<p>
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().
</p>
<p>
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.
</p>
<p>
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]).
</p>
<p>
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.
</p>
TicketkdilksFri, 15 Feb 2013 20:50:26 GMT
https://trac.sagemath.org/ticket/14126#comment:8
https://trac.sagemath.org/ticket/14126#comment:8
<p>
But for what it's worth, I was successfully able to apply the latest version of the patch.
</p>
TicketcsarSat, 16 Feb 2013 23:50:35 GMT
https://trac.sagemath.org/ticket/14126#comment:9
https://trac.sagemath.org/ticket/14126#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14126#comment:6" title="Comment 6">ncohen</a>:
</p>
<blockquote class="citation">
<p>
<code>O_o</code>
</p>
<p>
Well, shouldn't the two codes that compute the number of linear extensions be at the same place ?... A choice could be madebetween the two with an argument to <code>cardinality()</code>.
</p>
<p>
Nathann
</p>
</blockquote>
<p>
Fair point. <code>cardinality()</code> doesn't seem to live in <code>sage.combinat.posets.linear_extensions</code>, though. It looks like it comes from the <code>FiniteEnumeratedSets</code> category. Is it legitimate to give <code>LinearExtensionsOfPoset</code> a cardinality function with an argument to choose between the <code>_cardinality_from_iterator</code> from <code>FiniteEnumeratedSets</code> and counting recursively? My understanding of how categories are meant to work does not extend this far.
</p>
TicketncohenSun, 17 Feb 2013 19:36:40 GMT
https://trac.sagemath.org/ticket/14126#comment:10
https://trac.sagemath.org/ticket/14126#comment:10
<p>
Hellooooooooo !!
</p>
<blockquote class="citation">
<p>
Fair point. <code>cardinality()</code> doesn't seem to live in <code>sage.combinat.posets.linear_extensions</code>, though. It looks like it comes from the <code>FiniteEnumeratedSets</code> category.
</p>
</blockquote>
<p>
Oh. Right. So it builds all linear extensions then counts them <code>-_-</code>
</p>
<blockquote class="citation">
<p>
Is it legitimate to give <code>LinearExtensionsOfPoset</code> a cardinality function with an argument to choose between the <code>_cardinality_from_iterator</code> from <code>FiniteEnumeratedSets</code> and counting recursively? My understanding of how categories are meant to work does not extend this far.
</p>
</blockquote>
<p>
My understanding of categories is that when they prevent you from doing something you need then categories should be changed to allow you to do whatever you wanted to do in the first place.
</p>
<p>
Technically I do not think that categories would mind an optional argument to .cardinality. I guess that they would not notice it, so that's all good.
</p>
<p>
This being said, if you are at the Sage Days 45 right now Nicolas Thiery should be around. And he's THE guy you should bug for anything related to categories <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketnthierySat, 23 Feb 2013 16:29:00 GMT
https://trac.sagemath.org/ticket/14126#comment:11
https://trac.sagemath.org/ticket/14126#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14126#comment:10" title="Comment 10">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Fair point. <code>cardinality()</code> doesn't seem to live in <code>sage.combinat.posets.linear_extensions</code>, though. It looks like it comes from the <code>FiniteEnumeratedSets</code> category.
</p>
</blockquote>
<p>
Oh. Right. So it builds all linear extensions then counts them <code>-_-</code>
</p>
</blockquote>
<p>
To be precise, for an object in <a class="missing wiki">FiniteEnumeratedSets?</a>, cardinality is
set by default to _cardinality_from_iterator. So it indeed goes
through all linear extensions. However the counting is done along the
way, without storing them. So the memory complexity is roughly
constant (well, linear in the size of one linear extension).
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Is it legitimate to give <code>LinearExtensionsOfPoset</code> a cardinality
function with an argument to choose between the
<code>_cardinality_from_iterator</code> from <code>FiniteEnumeratedSets</code> and
counting recursively? My understanding of how categories are meant
to work does not extend this far.
</p>
</blockquote>
</blockquote>
<p>
+1
</p>
<blockquote class="citation">
<p>
My understanding of categories is that when they prevent you from
doing something you need then categories should be changed to allow
you to do whatever you wanted to do in the first place.
</p>
</blockquote>
<p>
Certainly: in any object oriented system, abstract classes are here to
provide you with default implementations. By design they are meant to
be overridden whenever there is a better algorithm in a special case
and the application in mind makes it worth it to implement that
algorithm
</p>
<p>
Categories are nothing but a way to organize those abstract classes.
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketcsarSat, 06 Jul 2013 16:21:54 GMT
https://trac.sagemath.org/ticket/14126#comment:12
https://trac.sagemath.org/ticket/14126#comment:12
<p>
I will give <code>LinearExtensionsOfPoset</code> the choice of which method to count linear extensions.
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/14126#comment:13
https://trac.sagemath.org/ticket/14126#comment:13
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/14126#comment:14
https://trac.sagemath.org/ticket/14126#comment:14
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/14126#comment:15
https://trac.sagemath.org/ticket/14126#comment:15
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/14126#comment:16
https://trac.sagemath.org/ticket/14126#comment:16
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketjmantysaloMon, 27 Jul 2015 19:33:49 GMTcc changed
https://trac.sagemath.org/ticket/14126#comment:17
https://trac.sagemath.org/ticket/14126#comment:17
<ul>
<li><strong>cc</strong>
<em>jmantysalo</em> added
</li>
</ul>
TicketjmantysaloTue, 28 Jul 2015 05:39:48 GMT
https://trac.sagemath.org/ticket/14126#comment:18
https://trac.sagemath.org/ticket/14126#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14126#comment:7" title="Comment 7">kdilks</a>:
</p>
<blockquote class="citation">
<p>
There's a fast way to count chains that doesn't involve iterating over all of them.
</p>
</blockquote>
<p>
What is it?
</p>
<p>
If there are several ways to do this, none of which is best from all sides, shouldn't we then have <code>algorithm</code>-keyword for the function? And in any version I guess that the poset should first be splitted to connected parts.
</p>
<p>
Is there something wrong with making a function with dumb implementation first? Then we would have a reference implementation, docstring and already thinked interface and place for the function.
</p>
TicketjmantysaloThu, 08 Oct 2015 07:26:05 GMTbranch set
https://trac.sagemath.org/ticket/14126#comment:19
https://trac.sagemath.org/ticket/14126#comment:19
<ul>
<li><strong>branch</strong>
set to <em>u/jmantysalo/count-lin-ext</em>
</li>
</ul>
TicketgitThu, 08 Oct 2015 07:27:30 GMTcommit set
https://trac.sagemath.org/ticket/14126#comment:20
https://trac.sagemath.org/ticket/14126#comment:20
<ul>
<li><strong>commit</strong>
set to <em>f908696aa7c63cefbc382af326cfe085e0dfa522</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f908696aa7c63cefbc382af326cfe085e0dfa522"><span class="icon"></span>f908696</a></td><td><code>Added counting of linear extensions without listing them.</code>
</td></tr></table>
TicketjmantysaloThu, 08 Oct 2015 07:34:56 GMT
https://trac.sagemath.org/ticket/14126#comment:21
https://trac.sagemath.org/ticket/14126#comment:21
<p>
I just tested how much we could save by just mechanically copying the code.
</p>
<p>
After <code>P6 = Posets(6).list()</code> it took 0.45 seconds to compute <code>sum([len(P.linear_extensions().list()) for P in P6])</code>, and 0.11 second to <code>sum([P.linear_extensions().count() for P in P6])</code>. For 14-element <code>Posets.TamariLattice(4)</code> it took 1.42 seconds to compute list of linear extensions and 0.24 seconds to just count them. Is this speedup useful?
</p>
<p>
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?
</p>
TicketkdilksFri, 09 Oct 2015 17:21:16 GMT
https://trac.sagemath.org/ticket/14126#comment:22
https://trac.sagemath.org/ticket/14126#comment:22
<p>
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.
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
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.
</p>
TicketjmantysaloFri, 09 Oct 2015 17:28:24 GMT
https://trac.sagemath.org/ticket/14126#comment:23
https://trac.sagemath.org/ticket/14126#comment:23
<p>
Well, counting linear extensions is #P-problem, I think. Of course it's complexity can still be <code>O(1.001^n)</code>...
</p>
<p>
But I will wait and see. At least my quick and dirty implementation gives a way to check the results of better code.
</p>
TicketjmantysaloMon, 21 Dec 2015 18:59:24 GMT
https://trac.sagemath.org/ticket/14126#comment:24
https://trac.sagemath.org/ticket/14126#comment:24
<p>
Pinging this one...
</p>
<p>
About faster algorithms: I am quite sure that we can do better in some cases. For example if you do a series-parallel decomposition, then counting can be done to indecomposable parts and just summed up with simpler formula.
</p>
<p>
But still, this is proven to be <code>#P</code>.
</p>
TicketchapotonTue, 12 Jul 2016 08:15:28 GMTauthor changed
https://trac.sagemath.org/ticket/14126#comment:25
https://trac.sagemath.org/ticket/14126#comment:25
<ul>
<li><strong>author</strong>
changed from <em>aschilling, nthiery, hivert</em> to <em>Anne Schilling, Nicolas M. Thiéry, Florent Hivert</em>
</li>
</ul>
TicketjmantysaloTue, 12 Jul 2016 08:23:29 GMT
https://trac.sagemath.org/ticket/14126#comment:26
https://trac.sagemath.org/ticket/14126#comment:26
<p>
?? Current version is written by me. (But of course it is trivial modification that just basically still counts all linear extensions.)
</p>
TicketchapotonTue, 12 Jul 2016 08:24:43 GMT
https://trac.sagemath.org/ticket/14126#comment:27
https://trac.sagemath.org/ticket/14126#comment:27
<p>
I was just cleaning a few invalid author fields. Please change it.
</p>
TicketjmantysaloTue, 12 Jul 2016 08:27:50 GMTauthor changed
https://trac.sagemath.org/ticket/14126#comment:28
https://trac.sagemath.org/ticket/14126#comment:28
<ul>
<li><strong>author</strong>
changed from <em>Anne Schilling, Nicolas M. Thiéry, Florent Hivert</em> to <em>Jori Mäntysalo</em>
</li>
</ul>
TicketkdilksTue, 12 Jul 2016 13:27:53 GMT
https://trac.sagemath.org/ticket/14126#comment:29
https://trac.sagemath.org/ticket/14126#comment:29
<p>
I am still intending on figuring out the 'right' way to do this. After recently realizing I can make the method be on the Hasse diagram, and can assume that I'm working with a naturally labelled poset on <code>0...n-1</code> with a dictionary of covering relations, I should be able to make it work.
</p>
TicketjmantysaloTue, 12 Jul 2016 14:07:05 GMT
https://trac.sagemath.org/ticket/14126#comment:30
https://trac.sagemath.org/ticket/14126#comment:30
<p>
I don't quite understand. AFAIK it is proved that counting linear extensions is in <code>#P</code>, and according to <a class="ext-link" href="http://link.springer.com/chapter/10.1007%2F11537311_39"><span class="icon"></span>http://link.springer.com/chapter/10.1007%2F11537311_39</a> there is an algorithm that lists them in linear time.
</p>
<p>
We can trivially reduce time by doing series-parallel decomposition first. It won't help on average.
</p>
<p>
So do you have some good algorithm in mind? Being in <code>#P</code> does not mean that <code>k</code> could not be improved in <code>O(k^n)</code>.
</p>
TicketkdilksTue, 12 Jul 2016 15:05:26 GMT
https://trac.sagemath.org/ticket/14126#comment:31
https://trac.sagemath.org/ticket/14126#comment:31
<p>
The <code>#P</code> 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.
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
If we wanted to keep the code simple, we could just create the lattice of order ideals <code>J(P)</code> 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 <code>0...(|I|-1)</code> (where <code>|I|</code> 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.
</p>
<p>
However, there should be some wizardry that lets us quickly create a dictionary on <code>0 .. (|I|-1)</code> corresponding to the up edges in <code>J(P)</code>. That wizardry is what I'm trying to figure out.
</p>
<p>
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) .
</p>
<p>
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.
</p>
TicketjmantysaloTue, 12 Jul 2016 18:07:25 GMT
https://trac.sagemath.org/ticket/14126#comment:32
https://trac.sagemath.org/ticket/14126#comment:32
<p>
?? Isn't the concept of <code>#P</code> about counting something? And <a class="ext-link" href="http://link.springer.com/article/10.1007/BF00383444"><span class="icon"></span>http://link.springer.com/article/10.1007/BF00383444</a> seems to say that too. It is trivial to say that listing them takes more than polynomial time.
</p>
<p>
Of course there are easy answers for some posets. For the ordinal sum of <code>P</code> and <code>Q</code> the count is just product.
</p>
<p>
But I will wait for the code and see.
</p>
<p>
E: Something in lattice of ideals - but every ideal corresponds to an antichain, and counting antichains is in <code>#P</code> I think.
</p>
TicketkdilksTue, 12 Jul 2016 18:53:23 GMT
https://trac.sagemath.org/ticket/14126#comment:33
https://trac.sagemath.org/ticket/14126#comment:33
<p>
Whatever it is, asymptotics aren't particularly relevant when in practice we're not going past |P|>100.
</p>
<p>
Even without any wizardry, <code>P.order_ideals_lattice().chain_polynomial().leading_coefficient()</code> (the naive implementation I mentioned) is significantly faster than <code>P.linear_extensions().cardinality()</code> (which defaults to using the iterator and generates all of them). Twice as fast on the antichain of 8 elements, ten times as fast on <code>P=Posets.TamariLattice(4)</code> (14 elements, 20243 linear extensions), ~600 times as fast on <code>P=Posets.IntegerCompositions(5)</code> (16 elements, 1680384 linear extensions).
</p>
TicketjmantysaloTue, 12 Jul 2016 19:44:41 GMT
https://trac.sagemath.org/ticket/14126#comment:34
https://trac.sagemath.org/ticket/14126#comment:34
<p>
Very interesting! Must think about this.
</p>
<p>
And <code>as_ideals=False</code> will get still more speed.
</p>
TicketjmantysaloWed, 13 Jul 2016 11:49:08 GMT
https://trac.sagemath.org/ticket/14126#comment:35
https://trac.sagemath.org/ticket/14126#comment:35
<p>
This got more speed with even very basic implementation of maximal chains counting:
</p>
<pre class="wiki">def countmax(P):
L = P.level_sets()
c = {}
for l in L[0]:
c[l] = 1
for lev in L[1:]:
for l in lev:
c[l] = sum(c[i] for i in P.lower_covers(l))
return sum(c[i] for i in P.maximal_elements())
</pre><p>
If we have better way to make a order ideals lattice, it is a place for new ticket. It would be nice feature in itself.
</p>
<p>
Hmm... Assuming we have <code>n</code>-element poset <code>P</code> and corresponding <code>L=J(P)</code>, how we modify <code>L</code> when we add element <code>n+1</code> as a minimal element to <code>P</code>? I guess the algorithm should be done by thinking this.
</p>
TicketjmantysaloWed, 13 Jul 2016 18:40:18 GMT
https://trac.sagemath.org/ticket/14126#comment:36
https://trac.sagemath.org/ticket/14126#comment:36
<p>
I guess this is worth reading about order ideals lattice: <a class="ext-link" href="http://www.sciencedirect.com/science/article/pii/S0166218X00002584"><span class="icon"></span>http://www.sciencedirect.com/science/article/pii/S0166218X00002584</a>
</p>
TicketkdilksThu, 14 Jul 2016 20:31:47 GMT
https://trac.sagemath.org/ticket/14126#comment:37
https://trac.sagemath.org/ticket/14126#comment:37
<p>
After much staring at Maple code, I now mostly understand the algorithm to generate a naturally labelled poset isomorphic to the order ideal lattice given a naturally labelled poset.
</p>
<p>
The idea is similar to what you mentioned. Run a loop that takes the lattice of order ideals for P restricted to <code>{1,...,k}</code>, and think about what happens when you add <code>k+1</code>. You need to know which order ideal <code>I_{k+1}</code> corresponds to the principal order ideal generated by <code>k+1</code> (but with <code>k+1</code> removed, since we haven't added it to the poset yet).
</p>
<p>
Now, you create a list <code>K</code> of the order ideals that lie above <code>I_{k+1}</code> in your partial lattice of order ideals. Each of these is going to yield a new order ideal to add to your list (the corresponding ideal <code>I</code> plus the new <code>k+1</code>). Make sure that <code>K</code> is ordered so that our lattice of order ideals stayed naturally labelled. The relations you need to add are <code>I</code> is covered by <code>I</code> plus <code>k+1</code>, and for every relation <code>A</code> covers <code>B</code> in <code>K</code>, you're going to have to add <code>A</code> plus <code>k+1</code> covers <code>B</code> plus <code>k+1</code>.
</p>
<p>
The main subtlety is in creating and maintaining a helper list that will eventually tell you where <code>I_{k+1}</code> is by the time you reach the <code>k+1</code>st step. Call the list <code>L</code>, indexed by your poset elements, initialize it with all 1s. As you go along, after <code>k</code> iterations, the entry <code>L[j]</code> tells you which order ideal corresponds to <code>I_j</code> restricted to <code>1...k</code>. If you add something incomparable to <code>j</code>, then <code>I_j</code> restricted to <code>1...k+1</code> doesn't change. If you add something comparable to <code>j</code>, then <code>I_j</code> restricted to <code>1...k+1</code> is one of the things in <code>K</code> plus <code>k+1</code>. So if we started with <code>N</code> order ideals, and <code>I_j</code> restricted to <code>1...k</code> was the <code>r</code>th thing in <code>K</code>, then <code>I_j</code> restricted to <code>1...k+1</code> will be the <code>N+r</code>th thing, and we update <code>L</code> accordingly.
</p>
<p>
Since it might take me some time to actually sit down and implement this, I agree that it makes sense to just change the <code>P.linear_extensions().cardinality()</code> method to something simple like <code>P.order_ideals_lattice().chain_polynomial().leading_coefficient()</code> (maybe with an optional parameter allowing one to default back to the iterator). Then I can work on a separate ticket for generating a naturally labelled poset isomorphic to the order ideal lattice, which <code>P.linear_extensions().cardinality()</code> could eventually utilize.
</p>
TicketjmantysaloFri, 15 Jul 2016 06:32:20 GMT
https://trac.sagemath.org/ticket/14126#comment:38
https://trac.sagemath.org/ticket/14126#comment:38
<p>
Does that mean that <code>order_ideals_lattice()</code> will have an option to get a lattice with plain integers as elements? If so, we should now deprecate <code>as_ideal</code> keyword, as it is plain Boolean value. Or at least it sounds funny to have <code>as_ideal</code> with possible values <code>True</code>, <code>False</code> and <code>'integers'</code>.
</p>
TicketgitFri, 15 Jul 2016 06:52:14 GMTcommit changed
https://trac.sagemath.org/ticket/14126#comment:39
https://trac.sagemath.org/ticket/14126#comment:39
<ul>
<li><strong>commit</strong>
changed from <em>f908696aa7c63cefbc382af326cfe085e0dfa522</em> to <em>24bc3319d440b0172666a2cace440e20986e91b6</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=24bc3319d440b0172666a2cace440e20986e91b6"><span class="icon"></span>24bc331</a></td><td><code>Add cardinality() to linear extensions of poset.</code>
</td></tr></table>
TicketjmantysaloFri, 15 Jul 2016 06:59:19 GMTstatus changed
https://trac.sagemath.org/ticket/14126#comment:40
https://trac.sagemath.org/ticket/14126#comment:40
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Shall we then accept this solution, and later think about optimizing this in two different ways?
</p>
<p>
Series-parallel decomposition could be a good thing anyways.
</p>
TicketkdilksFri, 15 Jul 2016 13:40:28 GMT
https://trac.sagemath.org/ticket/14126#comment:41
https://trac.sagemath.org/ticket/14126#comment:41
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14126#comment:38" title="Comment 38">jmantysalo</a>:
</p>
<blockquote class="citation">
<p>
Does that mean that <code>order_ideals_lattice()</code> will have an option to get a lattice with plain integers as elements? If so, we should now deprecate <code>as_ideal</code> keyword, as it is plain Boolean value. Or at least it sounds funny to have <code>as_ideal</code> with possible values <code>True</code>, <code>False</code> and <code>'integers'</code>.
</p>
</blockquote>
<p>
Yes. It probably makes sense to deprecate <code>as_ideals</code>, and change it to a keyword like <code>representative</code> that defaults to <code>ideal</code>, but can also be <code>antichains</code> or <code>integers</code>.
</p>
<p>
I guess I'd want to quantify how much overhead calculating connected components and a series-parallel decomposition of the original Hasse diagram introduces (my guess is a little and lot, respectively) before making it part of every single computation. I feel like unless you explicitly construct something as an ordinal/disjoint sum of smaller posets (and thus should already know the decomposition), almost every poset you'd throw at this where you'd really need optimal performance is going to be connected and not have a series-parallel decomposition.
</p>
TicketjmantysaloFri, 15 Jul 2016 14:52:46 GMT
https://trac.sagemath.org/ticket/14126#comment:42
https://trac.sagemath.org/ticket/14126#comment:42
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14126#comment:41" title="Comment 41">kdilks</a>:
</p>
<blockquote class="citation">
<p>
Yes. It probably makes sense to deprecate <code>as_ideals</code>, and change it to a keyword like <code>representative</code> that defaults to <code>ideal</code>, but can also be <code>antichains</code> or <code>integers</code>.
</p>
</blockquote>
<p>
That could be done now; a little less time for new users to learn a feature to be deprecated.
</p>
<blockquote class="citation">
<p>
I guess I'd want to quantify how much overhead calculating connected components and a series-parallel decomposition of the original Hasse diagram introduces (my guess is a little and lot, respectively) before making it part of every single computation. I feel like unless you explicitly construct something as an ordinal/disjoint sum of smaller posets (and thus should already know the decomposition), almost every poset you'd throw at this where you'd really need optimal performance is going to be connected and not have a series-parallel decomposition.
</p>
</blockquote>
<p>
True, but then whole decomposition will be just one check to see that the poset can not be decomposed.
</p>
<p>
And in any case that should a place for it's own ticket.
</p>
TicketchapotonThu, 28 Jul 2016 07:38:00 GMTstatus, milestone changed; reviewer set
https://trac.sagemath.org/ticket/14126#comment:43
https://trac.sagemath.org/ticket/14126#comment:43
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-7.3</em>
</li>
</ul>
<p>
ok, looks good to me.
</p>
TicketvbraunSun, 07 Aug 2016 20:01:47 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/14126#comment:44
https://trac.sagemath.org/ticket/14126#comment:44
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/jmantysalo/count-lin-ext</em> to <em>24bc3319d440b0172666a2cace440e20986e91b6</em>
</li>
</ul>
Ticket