Opened 9 years ago
Closed 8 years ago
#12930 closed enhancement (fixed)
Poset of Alternating sign matrices
Reported by: | aschilling | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.6 |
Component: | combinatorics | Keywords: | alternating sign matrices, posets, days38 |
Cc: | sage-combinat, pierre.cagne@… | Merged in: | sage-5.6.beta0 |
Authors: | Pierre Cagne | Reviewers: | Frédéric Chapoton, Anne Schilling |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Implementation of the poset of alternating sign matrices
This is best done by implementing a bijection to monotone triangles (or contre tableaux). This was already done in MuPAD
One way of the bijection is already implemented::
sage: import sage.combinat.alternating_sign_matrix as asm sage: asm.from_contre_tableau([[1, 2, 3], [1, 2], [1]]) [0 0 1] [0 1 0] [1 0 0] sage: asm.from_contre_tableau([[1, 2, 3], [2, 3], [3]]) [1 0 0] [0 1 0] [0 0 1]
It remains to implement the reverse bijection, and the ASM lattice from the ContreTableaux? lattice.
Attachments (1)
Change History (30)
comment:1 Changed 9 years ago by
- Keywords days38 added
comment:2 follow-up: ↓ 3 Changed 9 years ago by
- Status changed from new to needs_review
comment:3 in reply to: ↑ 2 Changed 9 years ago by
- Cc pierre.cagne@… added
Replying to chapoton:
I have implemented the reverse bijection under the name "to_contre_tableau"
I have also implemented the lattice, but only for alternating sign matrices, because contre-tableau are not hashable.
Thanks Frederic for implementing this! However, at Sage Days 38 Pierre Cagne <pierre.cagne@…> also implemented this bijection and the poset. He got over the problem of nonhashable matrices. I recently contacted him to post his patch, but have not heard since. I added his e-mail to this ticket. Hopefully he will post his patch here as well.
Best wishes,
Anne
comment:4 Changed 9 years ago by
Sorry for the delay, I didn't have the time lately.
But as Anne said, I implemented it (with the help of Luis Serrano) and I used the occasion to do some cleaning in the file alternating_sign_matrix.py. In fact, there was some obsolete uses (like CombinatorialClass?) that I changed. I settled a factory pattern based on classes instead of functions to allow some 'isinstance'. An other issue was the lack of documentation about contre-tableaux : except Sage's documentation, I was unable to find anything about them, even a definition ! So this new implementation uses monotone triangles, that are pretty well referenced on the web. I kept the default definition through contre-tableaux, but consider it obsolete and recommend to work with monotone triangles (by putting the keyword 'use_monotone_triangles' as True when declaring the object, see documentation).
To get the lattice, just use the 'lattice' method of your object of type AlternatingSignMatrices? or MonotoneTriangles?. (I got round the non-hashability of the lists for the monotone triangles by making them tuples.)
Regards.
EDIT : that's my first patch, do I have to add my name as 'Authors' in the ticket ?
comment:5 Changed 9 years ago by
Well, I guess my patch is no longer useful.
- for the bot : apply only trac_12930-add_mt_lattice.patch
- Please replace my name by yours in the Author field
- The lattices should be lattices and not only posets, this has to be corrected.
comment:6 follow-up: ↓ 7 Changed 9 years ago by
comment:7 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 9 years ago by
Hi Pierre,
Thanks for your work on this. I will also put your patch on the sage-combinat server since it will be easier to review it that way.
Thanks,
Anne
comment:8 in reply to: ↑ 7 Changed 9 years ago by
Hi Pierre,
Here are some first comments on your patch:
- The doctest did not pass for me on /combinat/alternating_sign_matrix.py
sage -t "devel/sage-combinat/sage/combinat/alternating_sign_matrix.py" Exception raised by doctesting framework. Use -verbose for details. [14.0 s] ---------------------------------------------------------------------- The following tests failed: sage -t "devel/sage-combinat/sage/combinat/alternating_sign_matrix.py" # Exception from doctest framework Total time for all tests: 14.0 seconds d099:combinat anne$ sage -t -verbose alternating_sign_matrix.py sage -t -verbose "devel/sage-combinat/sage/combinat/alternating_sign_matrix.py" Traceback (most recent call last): File "/Users/anne/.sage//tmp/alternating_sign_matrix_49336.py", line 805, in <module> runner=runner) File "/Applications/sage-5.0/local/bin/sagedoctest.py", line 54, in testmod_returning_runner runner=runner) File "/Applications/sage-5.0/local/bin/ncadoctest.py", line 1819, in testmod_returning_runner for test in finder.find(m, name, globs=globs, extraglobs=extraglobs): File "/Applications/sage-5.0/local/bin/ncadoctest.py", line 839, in find self._find(tests, obj, name, module, source_lines, globs, {}) File "/Applications/sage-5.0/local/bin/ncadoctest.py", line 893, in _find globs, seen) File "/Applications/sage-5.0/local/bin/ncadoctest.py", line 881, in _find test = self._get_test(obj, name, module, globs, source_lines) File "/Applications/sage-5.0/local/bin/ncadoctest.py", line 965, in _get_test filename, lineno) File "/Applications/sage-5.0/local/bin/ncadoctest.py", line 594, in get_doctest return DocTest(self.get_examples(string, name), globs, File "/Applications/sage-5.0/local/bin/ncadoctest.py", line 608, in get_examples return [x for x in self.parse(string, name) File "/Applications/sage-5.0/local/bin/ncadoctest.py", line 570, in parse self._parse_example(m, name, lineno) File "/Applications/sage-5.0/local/bin/ncadoctest.py", line 628, in _parse_example self._check_prompt_blank(source_lines, indent, name, lineno) File "/Applications/sage-5.0/local/bin/ncadoctest.py", line 715, in _check_prompt_blank line[indent:indent+3], line)) ValueError: line 13 of the docstring for __main__.example_18 lacks blank after ...: ' ....:' Exception raised by doctesting framework. Use -verbose for details. [1.4 s] ---------------------------------------------------------------------- The following tests failed: sage -t -verbose "devel/sage-combinat/sage/combinat/alternating_sign_matrix.py" # Exception from doctest framework Total time for all tests: 1.4 seconds
- You need doctests for all methods!!!
sage -coverage alternating_sign_matrix.py ---------------------------------------------------------------------- alternating_sign_matrix.py SCORE alternating_sign_matrix.py: 69% (25 of 36) Missing documentation: * __classcall_private__(cls, n, **kwds): * __init__(self, n, use_monotone_triangles=False): * __classcall_private__(cls, n, **kwds): * __init__(self, n): * __classcall_private__(cls, n, **kwds): * __classcall_private__(cls, n, **kwds): Missing doctests: * _lattice_initializer(self): * _lattice_initializer(self): * _is_a_cover(mt0, mt1): * _top_rows(row): * _triangular_arrangements_base(row): ----------------------------------------------------------------------
- Since to_monotone_triangle and from_montone_triangle are inverses of each other you could add some tests as follows:
sage: T = [[1, 2, 3], [1, 2], [1]] sage: asm.to_monotone_triangle(asm.from_monotone_triangle(T)) == T True
- Please add Examples to class AlternatingSignMatrices?(Parent) below line 87. In fact I would suggest to add EXAMPLES to all of your classes so that the user knows how to use them!
- Please use a line break on line 111 of your patch so that it is easier to read.
- Line 180 of your patch it says "Return a couple to use in argument of
Poset
. " Do you mean tuple instead of couple? Please add an EXAMPLES:: here so it is clear what the method does. A similar sentence appears in line 363.
- As Frederic also mentioned, in line 282 you might want to use Lattice instead of Poset.
- After line 324, please add an empty line.
- After line 374 the TESTS are missing!
- I would suggest to reuse all the doctests in the code that you are deleting since you want your new code to give the same answers as before. For example, I do not see the more systematic test such as
sage: [ AlternatingSignMatrices(n).cardinality() for n in range(0, 11)] [1, 1, 2, 7, 42, 429, 7436, 218348, 10850216, 911835460, 129534272700]
But please reuse all of it in the appropriate places.
- I think if you are removing code or renaming methods, you first need to "deprecate them" for one release cycle.
So much for now. Impressive work for a first patch!
Anne
comment:9 Changed 9 years ago by
- Description modified (diff)
- Reviewers set to Frederic Chapoton, Anne Schilling
- Status changed from needs_review to needs_work
comment:10 follow-up: ↓ 11 Changed 9 years ago by
Thanks for pointing those things out, Anne.
The failure you get with 'sage -t' is due to something weird about doctesting (cf #10458, you can't use multi-line tests due to some formattings by the IPython interactive shell). But removing this, I get a ton of others doctest failure : i'm working on it.
I notably get some failure about the tests which passed for the implementation with CombinatorialClass? because of the inherited methods like first(), last() or random_element(). By dropping out the inheritance in favor of Parent, we loose those kind of methods. However, the implementations of those are naive and do not bring any improvement in comparison with a user's straightforward implementation. For example, this is last() :
for i in self: pass return i
So I'm wondering about the usefulness of the reimplementation of those methods. Maybe can we skip them ? In fact, this is the only removing/renaming code (that we have to 'deprecate' so, but maybe as the CombinatorialClass? level directly). For the rest, I kept by default all the old implementation and allowed mine by keyword option. For example :
A = AlternatingSignMatrices(4) #inner implementation uses contre-tableaux as before A = AlternatingSignMatrices(4, use_monotone_triangles=True) #inner implementation uses monotone triangles as it should
Remark that some methods assert the use of monotone triangles (like lattice()).
I noticed also that EXAMPLES and TESTS are checked by 'sage -t' : is there a real difference between them ?
Regards,
Pierre
comment:11 in reply to: ↑ 10 ; follow-up: ↓ 12 Changed 9 years ago by
Hi Pierre,
The failure you get with 'sage -t' is due to something weird about doctesting (cf #10458, you can't use multi-line tests due to some formattings by the IPython interactive shell). But removing this, I get a ton of others doctest failure : i'm working on it.
Could you point me to the line in your code? I think if you use
...
instead of
...:
it should work.
I noticed that sometimes you do not repeat a definition (for example of A) from one doctest to the next. Is this the problem when you remove the offending doctest?
I notably get some failure about the tests which passed for the implementation with CombinatorialClass? because of the inherited methods like first(), last() or random_element(). By dropping out the inheritance in favor of Parent, we loose those kind of methods. However, the implementations of those are naive and do not bring any improvement in comparison with a user's straightforward implementation. For example, this is last() :
for i in self: pass return iSo I'm wondering about the usefulness of the reimplementation of those methods. Maybe can we skip them ?
Most likely skipping them is ok. Perhaps confirm this with Nicolas.
In fact, this is the only removing/renaming code (that we have to 'deprecate' so, but maybe as the CombinatorialClass? level directly). For the rest, I kept by default all the old implementation and allowed mine by keyword option. For example :
A = AlternatingSignMatrices(4) #inner implementation uses contre-tableaux as before A = AlternatingSignMatrices(4, use_monotone_triangles=True) #inner implementation uses monotone triangles as it should
Don't we want to get rid of the name contre-tableaux at some point? I was thinking of deprecating that name, so that at some point there would only be monotone_triangles.
I noticed also that EXAMPLES and TESTS are checked by 'sage -t' : is there a real difference between them ?
Yes, both are tested. For myself, I usually use EXAMPLES if these are tests that are also useful for the user to read to understand how the code is used. TESTS is for internal tests like in init or something like this or corner cases that need to be checked, but not necessarily read.
Best wishes,
Anne
comment:12 in reply to: ↑ 11 ; follow-up: ↓ 13 Changed 9 years ago by
Could you point me to the line in your code? I think if you use
...instead of
...:it should work.
Yes, that is the trick explained in #10458. But this is definitely something to fix : we want to be able to copy/paste our tests from the sage shell.
I noticed that sometimes you do not repeat a definition (for example of A) from one doctest to the next. Is this the problem when you remove the offending doctest?
Yes, it was careless mistakes. I fixed it.
Most likely skipping them is ok. Perhaps confirm this with Nicolas.
I think it is better too. I will contact Nicolas about that.
Don't we want to get rid of the name contre-tableaux at some point? I was thinking of deprecating that name, so that at some point there would only be monotone_triangles.
Well, yes. I was just thinking about compatibility with older code. But I can switch to monotone triangles only (or at least default) and go through a deprecation cycle.
Yes, both are tested. For myself, I usually use EXAMPLES if these are tests that are also useful for the user to read to understand how the code is used. TESTS is for internal tests like in init or something like this or corner cases that need to be checked, but not necessarily read.
Ok, thanks. I see now.
Pierre
comment:13 in reply to: ↑ 12 Changed 9 years ago by
Replying to PierreCagne:
Could you point me to the line in your code? I think if you use
...instead of
...:it should work.
Yes, that is the trick explained in #10458. But this is definitely something to fix : we want to be able to copy/paste our tests from the sage shell.
Sure, but the above works and you can use it for now for your patch to get the tests to pass!
I noticed that sometimes you do not repeat a definition (for example of A) from one doctest to the next. Is this the problem when you remove the offending doctest?
Yes, it was careless mistakes. I fixed it.
Did you post your new patch? When you do, could you please also put the new version on the sage-combinat server (well, if it is too complicated for you, I can do it, but it is easier to review this way for me).
Don't we want to get rid of the name contre-tableaux at some point? I was thinking of deprecating that name, so that at some point there would only be monotone_triangles.
Well, yes. I was just thinking about compatibility with older code. But I can switch to monotone triangles only (or at least default) and go through a deprecation cycle.
Yes, I think we should start the deprecation cycle.
Best wishes,
Anne
comment:14 follow-up: ↓ 15 Changed 9 years ago by
I am not aware of this sage-combinat server. But I will find out if it is easier for some reviewers to use it.
comment:15 in reply to: ↑ 14 Changed 9 years ago by
Replying to PierreCagne:
I am not aware of this sage-combinat server. But I will find out if it is easier for some reviewers to use it.
See http://wiki.sagemath.org/combinat/MercurialStepByStep But if you have not installed/used the sage-combinat queue, then do not worry about this. Just post the patch here and I will import it to the sage-combinat queue (which makes my reviewing easier).
Thanks,
Anne
comment:16 Changed 8 years ago by
- Description modified (diff)
I have done some clean-up work on the file.
apply only trac_12930-add_mt_lattice-v2
comment:17 Changed 8 years ago by
New patch, with clean-up of all whitespaces in the file.
comment:18 Changed 8 years ago by
- Reviewers changed from Frederic Chapoton, Anne Schilling to Frédéric Chapoton, Anne Schilling
comment:19 follow-up: ↓ 20 Changed 8 years ago by
- Description modified (diff)
comment:20 in reply to: ↑ 19 Changed 8 years ago by
Hi!
I just posted a slightly revised patch with some extra doctests and some clean-up in the documentation.
Please deprecate the old contre_tableaux methods and classes. Other than that, the patch seems to be finished.
Anne
comment:21 Changed 8 years ago by
For the bot:
apply only trac_12930-add_mt_lattice-as.patch
comment:22 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
apply only trac_12930-add_mt_lattice-v2.patch
I have added deprecations, but I am not sure that I have done it right. Could you please check ? Is it necessary to deprecate every single method in the classes of contre-tableaux ? I have not done that.
comment:23 Changed 8 years ago by
Well, it seems that something is going wrong with deprecations. I have no idea what to do. Did I make a mistake ? Is this because I have made the patch with a sage 5.2 ?
comment:24 Changed 8 years ago by
well, I removed some of the deprecations, that were seemingly misplaced. Probably one still has to deprecate every single function on contre tableaux.
comment:25 follow-up: ↓ 26 Changed 8 years ago by
apply only trac_12930-add_mt_lattice-v2.patch
comment:26 in reply to: ↑ 25 Changed 8 years ago by
Looks good now. I will set a positive review.
Anne
comment:27 Changed 8 years ago by
- Status changed from needs_review to positive_review
comment:28 Changed 8 years ago by
Thanks !
comment:29 Changed 8 years ago by
- Merged in set to sage-5.6.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
I have implemented the reverse bijection under the name "to_contre_tableau"
I have also implemented the lattice, but only for alternating sign matrices, because contre-tableau are not hashable.