#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 nthiery):
Replying to [comment:10 ncohen]:
> > Fair point. `cardinality()` doesn't seem to live in
`sage.combinat.posets.linear_extensions`, though. It looks like it comes
from the `FiniteEnumeratedSets` category.
>
> Oh. Right. So it builds all linear extensions then counts them `-_-`
To be precise, for an object in FiniteEnumeratedSets, 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).
> > Is it legitimate to give `LinearExtensionsOfPoset` a cardinality
> > function with an argument to choose between the
> > `_cardinality_from_iterator` from `FiniteEnumeratedSets` and
> > counting recursively? My understanding of how categories are meant
> > to work does not extend this far.
+1
> 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.
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
Categories are nothing but a way to organize those abstract classes.
Cheers,
Nicolas
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14126#comment:11>
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.