#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.


Reply via email to