Implement RSK for generalized permutations

[sagetrac-nborie]

Since the user is currently very strongly encouraged to use good formatting in #13742, there is no longer a good way to do certain methods which were more designed for words (ex. robinson_schensted())

Before, sage would accept that:

sage: Permutation([1,1,1,1,1])
[1, 1, 1, 1, 1]
sage: Permutation([-12,1,3])
[-12, 1, 3]

This ticket is to give an easy way to run RSK on the first one.

More explicitly, this ticket separates out the RSK into a global function which takes various types of input and runs the row insertion and also does the same for the inverse.

---

Apply only: attachment: trac_8392-check_permutation-ts.patch

Depends on #6495
Depends on #13605
Depends on #8703
Depends on #14459
Depends on #14319
Depends on #14302

CC: @sagetrac-sage-combinat @sagetrac-billey

Component: combinatorics

Keywords: permutation, check, days38, days45

Author: Travis Scrimshaw

Reviewer: Jeff Ferreira, Darij Grinberg

Merged: sage-5.11.beta0

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

[sagetrac-nborie]

Attachment: trac_8392_check_permutation-nb.patch.gz

[hivert]

comment:1

Hi Nicolas,

If you want your patch to be reviewed please check "needs review"...

For your information your patch breaks posets which use permutations starting from 0:

    sage: P = Posets.SymmetricGroupBruhatIntervalPoset([0,1,2,3], [2,3,0,1])
Exception raised:
...
    ValueError: [0, 1, 2, 3] is not a Standard permutations

[sagetrac-nborie]

comment:2

This patch is just a begining. I didn't check the 'needs review'. But really for now, I need the advises from any Veteran of combinatorics software....

See http://groups.google.com/group/sage-combinat-devel/browse_thread/thread/c6a39caca9df29dc

Thanks in advance.

[nthiery]

comment:3

The current patch breaks integer vectors; it would need to further fix WeightedIntegerVectors to not abuse anymore Permutation with multiple entries.

sage: WeightedIntegerVectors(8, [1,1,2]).list()
------------------------------------------------------------
Traceback (most recent call last):
  File "<ipython console>", line 1, in <module>
  File "/opt/sage-5.0.rc0/local/lib/python2.7/site-packages/sage/categories/finite_enumerated_sets.py", line 308, in list
    self._list = self._list_from_iterator()
  File "/opt/sage-5.0.rc0/local/lib/python2.7/site-packages/sage/categories/finite_enumerated_sets.py", line 142, in _list_from_iterator
    return [x for x in self]
  File "/opt/sage-5.0.rc0/local/lib/python2.7/site-packages/sage/combinat/integer_vector_weighted.py", line 259, in __iter__
    yield perm._left_to_right_multiply_on_right(Permutation_class(x))
  File "/opt/sage-5.0.rc0/local/lib/python2.7/site-packages/sage/combinat/permutation.py", line 910, in _left_to_right_multiply_on_right
    #Pad the permutations if they are of
  File "/opt/sage-5.0.rc0/local/lib/python2.7/site-packages/sage/combinat/permutation.py", line 286, in Permutation
    if n != len(l) or sorted(l) != range(1,n+1):
ValueError: the list l (=[0, 0, 4]) must contain each integer of {1,...,n} one time

[tscrim]

comment:4

Taking over to work on for Sage Days 38.

[tscrim]

Changed keywords from permutation, check, assert to permutation, check, assert, days38

[tscrim]

comment:5

I'm going to recycle this ticket due to #13742.

[tscrim]

Author: Travis Scrimshaw

[tscrim]

Changed keywords from permutation, check, assert, days38 to permutation, check, days38

[tscrim]

comment:6

For patchbot:

Apply: trac_8392-check_permutation-ts.patch

[tscrim]

Changed keywords from permutation, check, days38 to permutation, check, days38, days45

[tscrim]

comment:7

For patchbot:

Apply: trac_8392-check_permutation-ts.patch

[tscrim]

comment:8

Fixed doctests and updated documentation.

For patchbot:

Apply: trac_8392-check_permutation-ts.patch

[videlec]

comment:9

Hi,

The name of the ticket has nothing to do with what the ticket contains. You must change either one or the other !

Your changes to Word are not valid. Imagine that I am working on the alphabet of tableaux and I want a word of length two (containing two tableaux)...

Two comments, some others will come later

• sage/combinat/permutation.py, line 2905 you may change the ugly izip(list(range(1, len(self)+1)), self) with izip(xrange(1,len(self)+1), self)
• sage/combinat/rsk.py, line 114 "an method" -> "a method"

Vincent

[tscrim]

comment:10

I've made the changes. Now to construct a word using RSK, one will use the optional argument RSK_data.

For patchbot:

Apply: trac_8392-check_permutation-ts.patch

[tscrim]

comment:33

Fixed. Errors were due to references being in a function that had an alias.

[jdemeyer]

Changed dependencies from #6495 #13605 #8703 #14459 #14319 to #6495, #13605, #8703, #14459, #14319, #14302

[jdemeyer]

comment:35

This needs to be rebased such that it applies on top of #14302.

[tscrim]

Rebased

[tscrim]

comment:36

Attachment: trac_8392-check_permutation-ts.patch.gz

Rebased over #14302.

[jdemeyer]

Merged: sage-5.11.beta0

[saliola]

comment:38

Thanks for writing this patch. I support the proposed clean up of the code, but I want to raise an objection to choices in the user interface:

• I don't think that it is useful to deprecate the method robinson_schensted:

  DeprecationWarning: p.robinson_schensted() is deprecated. Use instead RSK(p)
  

  Telling users to use the RSK function instead of a method is not in the spirit of object-oriented programming. More importantly, it is totally unnecessary to deprecate the method.

• Also, I disagree with importing RSK, RSK_inverse, RobinsonSchenstedKnuth, RobinsonSchenstedKnuth_inverse into the global namespace when one object could easily handle all of these.

• Perhaps these names should not be capitalized since they are python functions and not classes. See the developers guide.

[anneschilling]

comment:39

I agree with Franco's comments!

Anne

[saliola]

comment:40

• The ability of doing RSK and EG is a great feature, but the documentation isn't very clear. What is [3,3,2] mean with EG insertion? Since it isn't a reduced word, how should this be interpreted? It's not invertible either:

sage: P, Q = RSK([3,3,2], insertion='EG')
sage: P
[[2, 3], [3]]
sage: Q
[[1, 2], [3]]
sage: RSK_inverse(P, Q, insertion='EG')
word: 232

• I would have expected that the output of RSK could be used as input to RSK_inverse:

sage: RSK_inverse(RSK([1,2]))
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-154-cb6c9a6f810d> in <module>()
----> 1 RSK_inverse(RSK([Integer(1),Integer(2)]))

TypeError: RSK_inverse() takes at least 2 arguments (1 given)

[tscrim]

comment:41

Hey Franco,

Replying to @saliola:

Thanks for writing this patch. I support the proposed clean up of the code, but I want to raise an objection to choices in the user interface:

• I don't think that it is useful to deprecate the method robinson_schensted:

  DeprecationWarning: p.robinson_schensted() is deprecated. Use instead RSK(p)
  

  Telling users to use the RSK function instead of a method is not in the spirit of object-oriented programming. More importantly, it is totally unnecessary to deprecate the method.

If we wanted to be fully OOP, then there needs to be a class of something like RSKUsable which has an abstract method RSK() where each type of object implements it's own version of RSK and RSKUsable would implement the row-insertion procedure. The problem with this is that we want to be able to handle (pairs of) lists, which we can't modify its class structure and I don't want to have to wrap a list as a word, and I also don't want to clutter up the MRO. Another reason why this is better as a function is most of the operation is independent of the type of object being passed in; all it does is it converts it into a pair of lists of the same size. Thus it provides a uniform interface for objects, and the fact that only permutations has such a method conflicts with this, so I think it is worthwhile to deprecate this.

• Also, I disagree with importing RSK, RSK_inverse, RobinsonSchenstedKnuth, RobinsonSchenstedKnuth_inverse into the global namespace when one object could easily handle all of these.

Then what is your proposed interface? If the input is a pair of tableaux as a list or is given as input 2 tableaux, then run the inverse? Hence we should combine two functions which do completely different behavior into one as I think of RSK as a procedure in 1 direction? What about if someone only thinks of this as the Robinson-Schensted bijection and tries RobinsonSchestead<tab>? This is why I setup these aliases and imported them.

• Perhaps these names should not be capitalized since they are python functions and not classes. See the developers guide.

For the full name, probably yes it should be changed. For the shortname RSK, it is an acronym, so I think it is better and more likely to be found than rsk. See the bottom of this section of the developers guide.

The ability of doing RSK and EG is a great feature, but the documentation isn't very clear. What is [3,3,2] mean with EG insertion? Since it isn't a reduced word, how should this be interpreted?

The documentation could use some expansion.

I would have expected that the output of RSK could be used as input to RSK_inverse:

This is because it's more logical to me for the input to be 2 arguments where we can explicitly specify what they are (as arguments), than a single parameter taking a list and checking to make sure it has length 2 and explaining the (non-standard IMO) input form in the docsting. We could handle both forms of input, but this seems overly complicated, and I imagine python programmers would simply use the * to expand the list as inputs as in the EG examples. This could probably use another example (maybe so far as a docstring explanation, but I'm hesitant about that) that's not for EG insertion.

Best,

Travis

[anneschilling]

comment:42

Hi Travis,

Replying to @tscrim:

If we wanted to be fully OOP, then there needs to be a class of something like RSKUsable which has an abstract method RSK() where each type of object implements it's own version of RSK and RSKUsable would implement the row-insertion procedure. The problem with this is that we want to be able to handle (pairs of) lists, which we can't modify its class structure and I don't want to have to wrap a list as a word, and I also don't want to clutter up the MRO. Another reason why this is better as a function is most of the operation is independent of the type of object being passed in; all it does is it converts it into a pair of lists of the same size. Thus it provides a uniform interface for objects, and the fact that only permutations has such a method conflicts with this, so I think it is worthwhile to deprecate this.

If a user makes a permutation p, it would be natural to try p. to see all methods. Currently p.robinson_schensted() works and it is the most natural entry point. There is no reason to deprecate this method, it can just be a one-line function returning RSK(p).

• Also, I disagree with importing RSK, RSK_inverse, RobinsonSchenstedKnuth, RobinsonSchenstedKnuth_inverse into the global namespace when one object could easily handle all of these.

Then what is your proposed interface?

Couldn't you just use options for the inverse?

The ability of doing RSK and EG is a great feature, but the documentation isn't very clear. What is [3,3,2] mean with EG insertion? Since it isn't a reduced word, how should this be interpreted?

The documentation could use some expansion.

Right now it is not clear at all that the input to the Edelman-Greene correspondence are reduced words. Also, if you want to put all insertion algorithms in one method, it might be better to call it insertion_algorithms rather than RSK since RSK is just one of them and I as a user would not think that Edelman-Greene would be under RSK. Or you should have Edelman-Greene as a different method. Plus the documentation definitely needs more details! At least you need to explain what the input is with the various options.

Best,

Anne