Opened 6 years ago

Closed 6 years ago

#21606 closed enhancement (fixed)

LatticePoset: Add Alan Day's doubling construction

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.5
Component: combinatorics Keywords:
Cc: tscrim, chapoton, ​nthiery Merged in:
Authors: Jori Mäntysalo Reviewers: Martin Rubey
Report Upstream: N/A Work issues:
Branch: 39042a5 (Commits, GitHub, GitLab) Commit: 39042a592828a3026a2dc4ad23c990077486a564
Dependencies: Stopgaps:

Status badges

Description

This patch add Alan Day's doubling construction to finite lattices.

Also this contains a picture.

Change History (21)

comment:1 Changed 6 years ago by jmantysalo

  • Branch set to u/jmantysalo/doubling

comment:2 Changed 6 years ago by jmantysalo

  • Cc tscrim chapoton ​nthiery added
  • Commit set to 881b77f9382857378c085c8bcfca057a89be3611
  • Status changed from new to needs_review

Nicolas: This is an answer to your comment "YES!" on thread https://groups.google.com/forum/#!topic/sage-devel/3YKltRTZ4vM

This code should be reviewed. But what's more important, is this kind of picture a good idea at all? I think that Nicolas was only one to comment my question about one year ago.

And if this is theoretically good idea, how about this picture? I do not have eyes for graphical things. A good example, or bad? If good, a good visualization or not?


New commits:

881b77fAdd Alan Days's doubling construction.

comment:3 follow-up: Changed 6 years ago by chapoton

may be more more economic to use labels 0 and 1 for the doubled elements in S (instead of 1 and 2)

comment:4 in reply to: ↑ 3 Changed 6 years ago by jmantysalo

Replying to chapoton:

may be more more economic to use labels 0 and 1 for the doubled elements in S (instead of 1 and 2)

What to do with non-doubled elements? Think about LatticePoset({1:[(1,1)], (1,1): [(1,1,1)]}) or something similar.

comment:5 follow-ups: Changed 6 years ago by chapoton

I was suggesting to use (i,0) when i is not doubled and (i,0) and (i,1) when i is doubled. But this is just a detail..

comment:6 in reply to: ↑ 5 Changed 6 years ago by jmantysalo

Replying to chapoton:

I was suggesting to use (i,0) when i is not doubled and (i,0) and (i,1) when i is doubled. But this is just a detail..

Ah, OK. Can be done.

What about the picture?

comment:7 Changed 6 years ago by jmantysalo

Ping. Any comments about the picture?

If I got none, I'll remove it and just add for code review.

comment:8 follow-up: Changed 6 years ago by mantepse

  • Reviewers set to Martin Rubey
  • Status changed from needs_review to positive_review

I think this is very nice, and indeed the picture makes it clearer than plotting the poset. Perhaps adding

sage: L = LatticePoset({0:["a"], "a":["b","c"], "b":[1], "c":[1]})
sage: L.day_doubling(["a", "b", "c"])
Finite lattice containing 8 elements

is helpful. Maybe you also want

The subset `S` is assumed to be :meth:`convex <sage.combinat.posets.hasse_diagram.HasseDiagram.is_convex_subset>` and connected.

In any case, I tried it on a few examples and I like it.

comment:9 in reply to: ↑ 5 Changed 6 years ago by jmantysalo

  • Status changed from positive_review to needs_work

Back to needs_work because of this:

Replying to chapoton:

I was suggesting to use (i,0) when i is not doubled and (i,0) and (i,1) when i is doubled. But this is just a detail..

and for your comments. Big thanks for checking the picture!

comment:10 in reply to: ↑ 8 Changed 6 years ago by jmantysalo

Replying to chapoton:

I was suggesting to use (i,0) when i is not doubled and (i,0) and (i,1) when i is doubled.

At least this made the code shorter. Hopefully I did not introduce bugs, please check.

Replying to mantepse:

I think this is very nice, and indeed the picture makes it clearer than plotting the poset.

Yep, automatically made plots are about never as good as hand-made, and Sage is not even a good at drawing. But still I think that the picture made by me is ugly. Hopefully some day someone with better color eye will change it.

Perhaps adding

sage: L = LatticePoset({0:["a"], "a":["b","c"], "b":[1], "c":[1]})
sage: L.day_doubling(["a", "b", "c"])
Finite lattice containing 8 elements

is helpful.

I think that it should be easy to write by the user, there is already one example.

Maybe you also want

The subset `S` is assumed to be :meth:`convex <sage.combinat.posets.hasse_diagram.HasseDiagram.is_convex_subset>` and connected.

Hasse diagram is kind of internal documentation, so I just spelled out in the main text what convex and connected means.

comment:11 Changed 6 years ago by jmantysalo

  • Milestone changed from sage-7.4 to sage-7.5
  • Status changed from needs_work to needs_review

comment:12 Changed 6 years ago by git

  • Commit changed from 881b77f9382857378c085c8bcfca057a89be3611 to 76836e5facf4b56389fd0348ec3c35ac163d9444

Branch pushed to git repo; I updated commit sha1. New commits:

b0ca572Add Alan Days's doubling construction.
3990cfcModify labeling of resulting lattice.
76836e5Rebase

comment:13 Changed 6 years ago by mantepse

Looks good to me. If you want to, you may replace

Resulting lattice `L[S]` has elements 

with

The resulting lattice `L[S]` has elements

I'm still compiling (wrong computer)

comment:14 Changed 6 years ago by git

  • Commit changed from 76836e5facf4b56389fd0348ec3c35ac163d9444 to 61c9e79b7a8bd7f3214db296f4a4b3a81e355068

Branch pushed to git repo; I updated commit sha1. New commits:

61c9e79Add 'the'.

comment:15 Changed 6 years ago by mantepse

  • Status changed from needs_review to positive_review

Looks good!

comment:16 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

Output order of these tests is not deterministic:

1994sage -t --long src/sage/combinat/posets/lattices.py
1995**********************************************************************
1996File "src/sage/combinat/posets/lattices.py", line 2450, in sage.combinat.posets.lattices.FiniteLatticePoset.day_doubling
1997Failed example:
1998    L2.upper_covers((1, 0))
1999Expected:
2000    [(2, 0), ('a', 0), ('b', 0)]
2001Got:
2002    [(2, 0), ('b', 0), ('a', 0)]
2003**********************************************************************
2004File "src/sage/combinat/posets/lattices.py", line 2452, in sage.combinat.posets.lattices.FiniteLatticePoset.day_doubling
2005Failed example:
2006    L2.upper_covers(('b', 0))
2007Expected:
2008    [('d', 0), ('b', 1), ('c', 0)]
2009Got:
2010    [('c', 0), ('b', 1), ('d', 0)]
2011**********************************************************************
20121 item had failures:
2013   2 of   9 in sage.combinat.posets.lattices.FiniteLatticePoset.day_doubling
2014    [394 tests, 2 failures, 2.42 s]

comment:17 Changed 6 years ago by git

  • Commit changed from 61c9e79b7a8bd7f3214db296f4a4b3a81e355068 to 39042a592828a3026a2dc4ad23c990077486a564

Branch pushed to git repo; I updated commit sha1. New commits:

ba5ccc8Add Alan Days's doubling construction.
3604443Modify labeling of resulting lattice.
7ac6e98Add 'the'.
4bb3b55Doctest correction.
4081c1fRebase
39042a5Correct also test block.

comment:18 follow-up: Changed 6 years ago by tscrim

  • Status changed from needs_work to positive_review

For future reference, an easier solution (and somewhat easier to understand) is to call sorted and have the output be the list.

comment:19 in reply to: ↑ 18 Changed 6 years ago by jmantysalo

Replying to tscrim:

For future reference, an easier solution (and somewhat easier to understand) is to call sorted and have the output be the list.

How? Python3 forbids 'a' < 1 and sorted(['a', 1]).

comment:20 Changed 6 years ago by tscrim

sorted(['a',1], key=str) works.

comment:21 Changed 6 years ago by vbraun

  • Branch changed from u/jmantysalo/doubling to 39042a592828a3026a2dc4ad23c990077486a564
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.