Opened 9 years ago

Closed 9 years ago

#14267 closed enhancement (fixed)

alternative algorithm for the lattice of order ideals of a poset

Reported by: chapoton Owned by: sage-combinat
Priority: minor Milestone: sage-5.12
Component: combinatorics Keywords: poset
Cc: sage-combinat Merged in: sage-5.12.beta1
Authors: Frédéric Chapoton Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by chapoton)

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

Attachments (1)

trac_14267_J_algo_fc.patch (3.3 KB) - added by chapoton 9 years ago.

Download all attachments as: .zip

Change History (6)

comment:1 Changed 9 years ago by chapoton

  • Component changed from PLEASE CHANGE to combinatorics
  • Owner changed from tbd to sage-combinat

Changed 9 years ago by chapoton

comment:2 Changed 9 years ago by chapoton

  • Description modified (diff)
  • Status changed from new to needs_review

comment:3 Changed 9 years ago by ncohen

  • Authors set to Frédéric Chapoton
  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

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

comment:4 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.12.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.