Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

alternative algorithm for the lattice of order ideals of a poset #14267

Closed
fchapoton opened this issue Mar 14, 2013 · 6 comments
Closed

alternative algorithm for the lattice of order ideals of a poset #14267

fchapoton opened this issue Mar 14, 2013 · 6 comments
Assignees
@sagetrac-sage-combinat
Labels
c: combinatorics p: minor / 4 t: enhancement
Milestone
sage-5.12

Comments

@fchapoton
Copy link
Contributor

I propose to implement another algorithm, which seems to be slightly faster than the existing implementation, at the cost of being defined on antichains instead of order ideals.

sage: P = Posets.ChainPoset(5)  
sage: Q = P.product(P)          
sage: R1 = Q.order_ideals_lattice();R1
Finite lattice containing 252 elements
sage: R2 = Q.order_ideals_lattice(as_ideals=False);R2
Finite lattice containing 252 elements
sage: R1.is_isomorphic(R2)
True
sage: timeit('Q.order_ideals_lattice()')
5 loops, best of 3: 5.25 s per loop
sage: timeit('Q.order_ideals_lattice(as_ideals=False)')                 
5 loops, best of 3: 3.45 s per loop

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: poset

Author: Frédéric Chapoton

Reviewer: Nathann Cohen

Merged: sage-5.12.beta1

Issue created by migration from https://trac.sagemath.org/ticket/14267
@fchapoton fchapoton added this to the sage-5.11 milestone Mar 14, 2013
@fchapoton
Copy link
Contributor Author

Attachment: trac_14267_J_algo_fc.patch.gz

@fchapoton

This comment has been minimized.

Sign in to view
@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Jun 25, 2013

comment:3

This patch is good to go, but why is there a poset file in categories/ while most of the poset stuff seems to be in combinat/posets ? O_o

Nathann

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Jun 25, 2013

Reviewer: Nathann Cohen

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Jun 25, 2013

Author: Frédéric Chapoton

@jdemeyer jdemeyer modified the milestones: sage-5.11, sage-5.12 Jul 21, 2013
@jdemeyer
Copy link

Merged: sage-5.12.beta1

@jessicapalencia jessicapalencia mannequin mentioned this issue Aug 20, 2013
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@sagetrac-sage-combinat sagetrac-sage-combinat

Labels
c: combinatorics p: minor / 4 t: enhancement
Projects
None yet
Milestone
sage-5.12
Development

No branches or pull requests
2 participants
@jdemeyer @fchapoton