improvements and additions to dyck_words.py

[zabrocki]

Add functionality to DyckWord and DyckWords classes including:

• the ability to input a Dyck word by specifying the area sequence of the corresponding path
• injections/surjections to other combinatorial objects (e.g. touch composition, Haglund's area<->bounce map, etc.)
• combinatorial statistics (e.g. number of touch points, length of first/last run, area, bounce, dinv)
• connections with symmetric functions
• a pretty print function

It moreover makes the distinction (ie implements two different classes DyckWords_class and DyckWords_complete between complete Dyck words and uncomplete ones, since many methods are only defined for complete Dyck words.

CC: @zabrocki @sagetrac-DorotaMazur @stumpc5 @hivert

Component: combinatorics

Keywords: dyck_words, noncrossing partitions, parking functions

Author: Mike Zabrocki

Reviewer: Christian Stump

Merged: sage-5.5.beta2

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

[zabrocki]

Changed dependencies from #11641 to none

[zabrocki]

Changed keywords from none to dyck_words, noncrossing partitions, parking functions

[fchapoton]

comment:2

You should add doctests to all fonctions.

And try not to insert new trailing whitespaces.

Two doctests are failing. They seem to be caused by changes in other places. Just change them to their new value.

[zabrocki]

comment:3

I think I got the trailing whitespaces. I had a mistake when I searched for them before.
I changed doc-tests failing in combinat/q_analogues.py and misc/latex.py.
I am not seeing the missing doc-tests.

Christian has asked to resolve a question about if we should join functions of the form .to_xyz_avoiding_permutation() to a .to_permutation() function in https://groups.google.com/d/msg/sage-combinat-devel/jzGHkbcrLec/9WurflNlyEoJ

[fchapoton]

comment:4

there should be 3 missing docs :

one of them is the __init__ of DyckWord_class

and b_statistic and a_statistic, which are no longer tested !

[fchapoton]

comment:5

maybe rather use deprecated_function_alias (see https://github.com/sagemath/sage-prod/files/10655763/trac_13109-documentation.v3.patch.gz)

[zabrocki]

comment:6

Thanks! I've added the init doctests and I used the deprecated_function_alias. I also added a check in min_from_heights that the first entry is 0 (as existed in from_heights method).

[fchapoton]

comment:8

Christian, is your patch supposed to replace the previous one ?

[stumpc5]

comment:9

Replying to @fchapoton:

Christian, is your patch supposed to replace the previous one ?

No. I haven't yet checked why my patch doesn't apply on 5.4.rc3. I plan to do this as soon as the sage-combinat queue (containing Mike's last changes) is working again -- I hope this to happen today!

[stumpc5]

comment:10

Replying to @stumpc5:

Replying to @fchapoton:

Christian, is your patch supposed to replace the previous one ?

No. I haven't yet checked why my patch doesn't apply on 5.4.rc3. I plan to do this as soon as the sage-combinat queue (containing Mike's last changes) is working again -- I hope this to happen today!

I uploaded the newest version of the patch containing Mike's and my changes. 5.4.rc3 is still compiling, I will check why it doesn't apply there as soon as it's ready (I am still using 5.3 currently).

[stumpc5]

comment:11

I uploaded the newest version of the patch containing Mike's and my changes. 5.4.rc3 is still compiling, I will check why it doesn't apply there as soon as it's ready (I am still using 5.3 currently).

Apparently, it was patchbot's mistake...

I now deleted the trailing whitespaces, and will finish my review tomorrow. Since I was doing many changes, I would then still hope that someone else is looking at these (but I guess Mike could do it as well).

Best, Christian

[stumpc5]

comment:12

Hi,

I'd give this ticket a positive review as is. Nonetheless, I would prefer if someone else is giving his/her okay as well since I made many changes in this ticket myself.

Two issues I somehow do not like with Dyck words (but, if desired, should be taken care of in another ticket) are:

• the __repr__ and the __str__ methods for Dyck words differ:

sage: D = DyckWord([1,1,1,0,1,0,0,1,1,0,0,0])
sage: D
[1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0]
sage: print D
((()())(()))

• We now distinguish between complete and uncomplete Dyck words (and implicitly did that before as well). But iterating through DyckWords only yield complete Dyck words.

sage: I = iter(DyckWords())                   
sage: for i in range(10):^J    print I.next() 
....:     

()
()()
(())
()()()
()(())
(())()
(()())
((()))
()()()()

Would you expect this behaviour? Are there better solutions for those?

Best, Christian

[zabrocki]

comment:13

I have looked at Christian's changes and approve. This patch is ready to go.

About the two issues:

• I don't object strongly to the !str! and the !repr! being different, but I can see that is a bit unusual. This patch adds a pretty_print method (and this isn't it at all), but we could rename !str!() to be .pp() or put an optional argument in .to_string(parens=True)

• I think that this seems like correct behavior to me. There isn't a natural way of iterating through incomplete DyckWords() that I would find particularly helpful. As it is, if you want to access incomplete Dyck words you need to specify the the number of open and close parentheses. That is DyckWords() is all complete DyckWords, DyckWords(n) is Dyck words with n open and n close and DyckWords(n,k) is Dyck words with n open and k close. The truth is, I don't have a use for iterating through all complete/incomplete Dyck words.

[jdemeyer]

comment:15

Please fill in your real names as Author and Reviewer.

[stumpc5]

Changed author from zabrocki to Mike Zabrocki

[stumpc5]

Changed reviewer from stumpc5 to Christian Stump

[jdemeyer]

comment:17

Why the change in latex.py? It causes doctest failures on various machines:

sage -t  --long -force_lib devel/sage/sage/misc/latex.py
**********************************************************************
File "/home/buildbot/build/sage/rosemary-1/rosemary_full/build/sage-5.5.beta2/devel/sage-main/sage/misc/latex.py", line 604:
    sage: print latex_extra_preamble()
Expected:
    \usepackage{tikz}
    <BLANKLINE>
    \newcommand{\ZZ}{\Bold{Z}}
    \newcommand{\NN}{\Bold{N}}
    \newcommand{\RR}{\Bold{R}}
    \newcommand{\CC}{\Bold{C}}
    \newcommand{\QQ}{\Bold{Q}}
    \newcommand{\QQbar}{\overline{\QQ}}
    \newcommand{\GF}[1]{\Bold{F}_{#1}}
    \newcommand{\Zp}[1]{\ZZ_{#1}}
    \newcommand{\Qp}[1]{\QQ_{#1}}
    \newcommand{\Zmod}[1]{\ZZ/#1\ZZ}
    \newcommand{\CDF}{\Bold{C}}
    \newcommand{\CIF}{\Bold{C}}
    \newcommand{\CLF}{\Bold{C}}
    \newcommand{\RDF}{\Bold{R}}
    \newcommand{\RIF}{\Bold{I} \Bold{R}}
    \newcommand{\RLF}{\Bold{R}}
    \newcommand{\CFF}{\Bold{CFF}}
    \newcommand{\Bold}[1]{\mathbf{#1}}
    <BLANKLINE>
Got:
    <BLANKLINE>
    \newcommand{\ZZ}{\Bold{Z}}
    \newcommand{\NN}{\Bold{N}}
    \newcommand{\RR}{\Bold{R}}
    \newcommand{\CC}{\Bold{C}}
    \newcommand{\QQ}{\Bold{Q}}
    \newcommand{\QQbar}{\overline{\QQ}}
    \newcommand{\GF}[1]{\Bold{F}_{#1}}
    \newcommand{\Zp}[1]{\ZZ_{#1}}
    \newcommand{\Qp}[1]{\QQ_{#1}}
    \newcommand{\Zmod}[1]{\ZZ/#1\ZZ}
    \newcommand{\CDF}{\Bold{C}}
    \newcommand{\CIF}{\Bold{C}}
    \newcommand{\CLF}{\Bold{C}}
    \newcommand{\RDF}{\Bold{R}}
    \newcommand{\RIF}{\Bold{I} \Bold{R}}
    \newcommand{\RLF}{\Bold{R}}
    \newcommand{\CFF}{\Bold{CFF}}
    \newcommand{\Bold}[1]{\mathbf{#1}}
    <BLANKLINE>
**********************************************************************

[zabrocki]

comment:18

The change to latex_extra_preamble came from a call to latex.add_package_to_preamble_if_available("tikz").  This was moved into its proper place and the change to latex.py was removed.  Christian will upload the patch since I don't have overwrite permission.

[stumpc5]

Attachment: trac_13550_dyck_wordsdinv-mz.patch.gz

[stumpc5]

comment:19

Replying to @zabrocki:

The change to latex_extra_preamble came from a call to latex.add_package_to_preamble_if_available("tikz").  This was moved into its proper place and the change to latex.py was removed.  Christian will upload the patch since I don't have overwrite permission.

done!

[zabrocki]

comment:20

Tests re-run and all pass. I am restoring the positive review.

[jdemeyer]

Merged: sage-5.5.beta2

[nathanncohen]

comment:22

I do not know who I should send this to, but the following line fails, at least on my computer

sage: view( DyckWord([1,0]))

This ticket is the last one which modified the .latex function of Dyck words.

Nathann