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.

[chapoton]

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]

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

[chapoton]

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 !

[chapoton]

maybe rather use deprecated_function_alias (see  http://trac.sagemath.org/sage_trac/attachment/ticket/13109/trac_13109-documentation.v3.patch)

[zabrocki]

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

[chapoton]

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

[stumpc5]

Replying to chapoton:

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]

Replying to stumpc5:

Replying to chapoton:

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]

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]

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]

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]

Please fill in your real names as Author and Reviewer.

[jdemeyer]

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]

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]

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]

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

[ncohen]

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