Poset of Alternating sign matrices

[aschilling]

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 trac_12930-add_mt_lattice-v2.patch​

[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.

[aschilling]

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

[PierreCagne]

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 ?

[chapoton]

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.

[aschilling]

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

[aschilling]

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

[PierreCagne]

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

[aschilling]

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

[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.

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

[aschilling]

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

[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.

[aschilling]

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

[chapoton]

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

apply only trac_12930-add_mt_lattice-v2

[chapoton]

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

[aschilling]

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

[chapoton]

For the bot:

apply only trac_12930-add_mt_lattice-as.patch

[chapoton]

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.

[chapoton]

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 ?

[chapoton]

clean-up

[chapoton]

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

[chapoton]

apply only trac_12930-add_mt_lattice-v2.patch

[aschilling]

Looks good now. I will set a positive review.

Anne

[chapoton]

Thanks !