#16985: Poset: Faster is_selfdual()
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: new
Priority: minor | Milestone: sage-wishlist
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/poset__faster_is_dual__|
17f1b0f71b8cb537bbe0a1dbdf7d350c0dd845b6
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by jmantysalo):
Simple test can be done with Sage without coding anything. For example
after `L=Posets(6).list()` I just got
`len([P for P in L if P.is_selfdual()])` -> CPU time: 60.21 s, Wall time:
65.77 s
`len([P for P in L if sorted(P._hasse_diagram.in_degree()) ==
sorted(P._hasse_diagram.out_degree()) and P.is_selfdual()])` -> CPU time:
38.73 s, Wall time: 40.53 s
`len([P for P in L if sorted(P._hasse_diagram.in_degree()) ==
sorted(P._hasse_diagram.out_degree()) and [len(x) for x in
P.level_sets()]==[len(x) for x in P.dual().level_sets()] and
P.is_selfdual()])` -> CPU time: 28.94 s, Wall time: 30.20 s
Difference grows bigger wiht `Posets(7)`, and is also bigger when coding
this directly to `.py`-file.
There are 318 posets of size 6. Of those 30 pass first test but fails
second, and 12 pass first and second test but fails last one. This is an
example of poset passing 1. and 2. test:
`Poset([[0,1,2,3,4,5],[[1, 5], [2, 3], [2, 5], [3, 4]]])`.
I can calculate these numbers for 7- and 8-element posets if needed.
--
Ticket URL: <http://trac.sagemath.org/ticket/16985#comment:7>
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.
