Poset of Alternating sign matrices #12930

anneschilling · 2012-05-09T16:27:48Z

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

http://mupad-combinat.svn.sourceforge.net/viewvc/mupad-combinat/trunk/MuPAD-Combinat/lib/COMBINAT/alternatingSignMatrices.mu?view=log

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.

Apply attachment: trac_12930-add_mt_lattice-v2.patch

CC: @sagetrac-sage-combinat @sagetrac-PierreCagne

Component: combinatorics

Keywords: alternating sign matrices, posets, days38

Author: Pierre Cagne

Reviewer: Frédéric Chapoton, Anne Schilling

Merged: sage-5.6.beta0

Issue created by migration from https://trac.sagemath.org/ticket/12930

The text was updated successfully, but these errors were encountered:

anneschilling · 2012-05-09T22:33:04Z

Changed keywords from alternating sign matrices, posets to alternating sign matrices, posets, days38

fchapoton · 2012-06-08T11:58:06Z

comment:2

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.

fchapoton · 2012-06-08T11:58:06Z

Author: Frédéric Chapoton

anneschilling · 2012-06-08T16:01:37Z

comment:3

Replying to @fchapoton:

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@ens.fr 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

sagetrac-PierreCagne · 2012-06-11T19:00:04Z

comment:4

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 ?

fchapoton · 2012-06-14T18:46:50Z

comment:5

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.

sagetrac-PierreCagne · 2012-06-14T19:43:24Z

Changed author from Frédéric Chapoton to Pierre Cagne

anneschilling · 2012-06-14T19:52:42Z

comment:7

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

anneschilling · 2012-06-14T21:03:34Z

comment:8

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

anneschilling · 2012-06-14T22:12:29Z

Reviewer: Frederic Chapoton, Anne Schilling

sagetrac-PierreCagne · 2012-06-15T14:26:23Z

comment:10

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

anneschilling · 2012-06-15T15:05:10Z

comment:11

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 i
So 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

sagetrac-PierreCagne · 2012-06-15T15:32:52Z

comment:12

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

anneschilling · 2012-06-15T22:02:26Z

comment:13

Replying to @sagetrac-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

sagetrac-PierreCagne · 2012-06-15T22:21:24Z

comment:14

I am not aware of this sage-combinat server. But I will find out if it is easier for some reviewers to use it.

anneschilling · 2012-06-15T22:36:18Z

comment:15

Replying to @sagetrac-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

fchapoton · 2012-09-20T16:18:44Z

comment:16

I have done some clean-up work on the file.

apply only trac_12930-add_mt_lattice-v2

fchapoton · 2012-09-22T09:52:19Z

comment:17

New patch, with clean-up of all whitespaces in the file.

fchapoton · 2012-09-24T11:38:27Z

Changed reviewer from Frederic Chapoton, Anne Schilling to Frédéric Chapoton, Anne Schilling

anneschilling · 2012-09-25T03:42:51Z

comment:20

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

fchapoton · 2012-10-19T08:13:18Z

comment:21

For the bot:

apply only trac_12930-add_mt_lattice-as.patch

fchapoton · 2012-10-29T13:08:44Z

comment:22

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.

fchapoton · 2012-10-29T14:03:08Z

comment:23

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 ?

fchapoton · 2012-10-29T19:18:36Z

clean-up

fchapoton · 2012-10-29T19:20:01Z

comment:24

Attachment: trac_12930-add_mt_lattice-v2.patch.gz

well, I removed some of the deprecations, that were seemingly misplaced. Probably one still has to deprecate every single function on contre tableaux.

fchapoton · 2012-10-29T19:21:26Z

comment:25

apply only trac_12930-add_mt_lattice-v2.patch

anneschilling · 2012-11-20T08:33:44Z

comment:26

Looks good now. I will set a positive review.

Anne

fchapoton · 2012-11-20T08:53:58Z

comment:28

Thanks !

jdemeyer · 2012-12-18T11:16:24Z

Merged: sage-5.6.beta0

anneschilling added this to the sage-5.6 milestone May 9, 2012

anneschilling added c: combinatorics labels May 9, 2012

anneschilling assigned sagetrac-sage-combinat May 9, 2012

fchapoton added the s: needs review label Jun 8, 2012

This comment has been minimized.

Sign in to view

anneschilling added s: needs work and removed s: needs review labels Jun 14, 2012

This comment has been minimized.

Sign in to view

fchapoton added s: needs review and removed s: needs work labels Oct 29, 2012

anneschilling added s: positive review and removed s: needs review labels Nov 20, 2012

jdemeyer removed the s: positive review label Dec 18, 2012

jdemeyer closed this as completed Dec 18, 2012

This was referenced Dec 29, 2012

Change default behaviour of Poset to facade = True #13747

Closed

Remove deprecated code from combinat/ #15466

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Poset of Alternating sign matrices #12930

Poset of Alternating sign matrices #12930

anneschilling commented May 9, 2012

anneschilling commented May 9, 2012

fchapoton commented Jun 8, 2012

fchapoton commented Jun 8, 2012

anneschilling commented Jun 8, 2012

sagetrac-PierreCagne mannequin commented Jun 11, 2012

fchapoton commented Jun 14, 2012

sagetrac-PierreCagne mannequin commented Jun 14, 2012

anneschilling commented Jun 14, 2012

anneschilling commented Jun 14, 2012

anneschilling commented Jun 14, 2012

This comment has been minimized.

sagetrac-PierreCagne mannequin commented Jun 15, 2012

anneschilling commented Jun 15, 2012

sagetrac-PierreCagne mannequin commented Jun 15, 2012

anneschilling commented Jun 15, 2012

sagetrac-PierreCagne mannequin commented Jun 15, 2012

anneschilling commented Jun 15, 2012

fchapoton commented Sep 20, 2012

This comment has been minimized.

fchapoton commented Sep 22, 2012

fchapoton commented Sep 24, 2012

This comment has been minimized.

anneschilling commented Sep 25, 2012

fchapoton commented Oct 19, 2012

This comment has been minimized.

fchapoton commented Oct 29, 2012

fchapoton commented Oct 29, 2012

fchapoton commented Oct 29, 2012

fchapoton commented Oct 29, 2012

fchapoton commented Oct 29, 2012

anneschilling commented Nov 20, 2012

fchapoton commented Nov 20, 2012

jdemeyer commented Dec 18, 2012

Poset of Alternating sign matrices #12930

Poset of Alternating sign matrices #12930

Comments

anneschilling commented May 9, 2012

anneschilling commented May 9, 2012

fchapoton commented Jun 8, 2012

fchapoton commented Jun 8, 2012

anneschilling commented Jun 8, 2012

sagetrac-PierreCagne mannequin commented Jun 11, 2012

fchapoton commented Jun 14, 2012

sagetrac-PierreCagne mannequin commented Jun 14, 2012

anneschilling commented Jun 14, 2012

anneschilling commented Jun 14, 2012

anneschilling commented Jun 14, 2012

This comment has been minimized.

sagetrac-PierreCagne mannequin commented Jun 15, 2012

anneschilling commented Jun 15, 2012

sagetrac-PierreCagne mannequin commented Jun 15, 2012

anneschilling commented Jun 15, 2012

sagetrac-PierreCagne mannequin commented Jun 15, 2012

anneschilling commented Jun 15, 2012

fchapoton commented Sep 20, 2012

This comment has been minimized.

fchapoton commented Sep 22, 2012

fchapoton commented Sep 24, 2012

This comment has been minimized.

anneschilling commented Sep 25, 2012

fchapoton commented Oct 19, 2012

This comment has been minimized.

fchapoton commented Oct 29, 2012

fchapoton commented Oct 29, 2012

fchapoton commented Oct 29, 2012

fchapoton commented Oct 29, 2012

fchapoton commented Oct 29, 2012

anneschilling commented Nov 20, 2012

fchapoton commented Nov 20, 2012

jdemeyer commented Dec 18, 2012