#8392 closed enhancement (fixed)
Implement RSK for generalized permutations
Reported by: | nborie | Owned by: | tscrim |
---|---|---|---|
Priority: | major | Milestone: | sage-5.11 |
Component: | combinatorics | Keywords: | permutation, check, days38, days45 |
Cc: | sage-combinat, billey | Merged in: | sage-5.11.beta0 |
Authors: | Travis Scrimshaw | Reviewers: | Jeff Ferreira, Darij Grinberg |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #6495, #13605, #8703, #14459, #14319, #14302 | Stopgaps: |
Description (last modified by )
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: trac_8392-check_permutation-ts.patch
Attachments (3)
Change History (45)
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Status changed from new to needs_work
comment:2 Changed 11 years ago by
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.
comment:3 Changed 9 years ago by
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
comment:4 Changed 9 years ago by
- Keywords days38 added
- Owner changed from nborie to tscrim
Taking over to work on for Sage Days 38.
comment:5 Changed 8 years ago by
- Description modified (diff)
- Keywords assert removed
I'm going to recycle this ticket due to #13742.
comment:6 Changed 8 years ago by
- Description modified (diff)
- Keywords days45 added
- Status changed from needs_work to needs_review
For patchbot:
Apply: trac_8392-check_permutation-ts.patch
comment:7 Changed 8 years ago by
For patchbot:
Apply: trac_8392-check_permutation-ts.patch
comment:8 Changed 8 years ago by
Fixed doctests and updated documentation.
For patchbot:
Apply: trac_8392-check_permutation-ts.patch
comment:9 Changed 8 years ago by
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
comment:10 Changed 8 years ago by
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
comment:11 Changed 8 years ago by
- Summary changed from Check when defining a permutation by one-line notation (list of int) to Implement RSK for generalized permutations
- Type changed from defect to enhancement
comment:12 Changed 8 years ago by
- Cc billey added
Vincent has told me that he is okay with the documentation and current implementation but cannot review the math. I'm cc-ing Sara since she was interested in this patch.
comment:14 Changed 8 years ago by
- Dependencies changed from #6495 to #6495 #13605
Minor documentation tweaks which depend on #13605.
For patchbot:
Apply: trac_8392-check_permutation-ts.patch
comment:15 Changed 8 years ago by
Forgot to refresh...
For patchbot:
Apply: trac_8392-check_permutation-ts.patch
comment:16 Changed 8 years ago by
Added Edelman-Greene insertion to the patch as well.
For patchbot:
Apply: trac_8392-check_permutation-ts.patch
comment:17 Changed 8 years ago by
- Dependencies changed from #6495 #13605 to #6495 #13605 #8703
Rebased over #8703.
comment:18 Changed 8 years ago by
- Dependencies changed from #6495 #13605 #8703 to #6495 #13605 #8703 #14459
Rebased over #14459.
comment:19 Changed 8 years ago by
- Dependencies changed from #6495 #13605 #8703 #14459 to #6495 #13605 #8703 #14459 #14319
Rebased over #14319 due to minor docstring conflicts.
comment:20 Changed 8 years ago by
- Description modified (diff)
For patchbot:
Apply trac_8392-check_permutation-ts.patch
comment:21 Changed 8 years ago by
I'm fussing about corner cases as usual, but I think this here might use some fix:
sage: Permutation([]) # This is be the identity permutation in S_0. [] sage: Permutation([]).cycle_string() # OK. '()' sage: Permutation('()') # This should give the S_0 identity back -- but it doesn't. [1] sage: Permutation('') # Does this maybe? No. --------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-29-3df27d9d4d7a> in <module>() ----> 1 Permutation('') /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/combinat/permutation.pyc in Permutation(l, check_input) 430 cycle_list = [] 431 for c in cycles: --> 432 cycle_list.append(map(int, c.split(","))) 433 434 return from_cycles(max([max(c) for c in cycle_list]), cycle_list) ValueError: invalid literal for int() with base 10: '' sage: Permutation(()) # What about this? [1]
Travis, why did you replace "standard" by "semi-standard" in robinson_schensted
?
comment:22 Changed 8 years ago by
I've just reviewed the math: trac_8392-review_patch-dg.patch.
Documentation extended (please check my formatting!), Edelman-Greene insertion fixed (it used to do the same as normal RSK), an is_increasing() method for tableaux added (since we're already doing Edelman-Greene...), and some more doc fixes made (including the changes that were formerly in #14131).
I have not fixed the issues in my previous comment; I don't know our stance on them.
comment:23 Changed 8 years ago by
Hey Darij,
I've folded your review patch in and made some additional tweaks to the docs. I can't believe how badly I coded the EG insertion. I reverted it back to standard since when I first wrote this patch, permutations could take inputs with repetition.
As for your previous comment, that is outside of the scope of this patch since it deals with input for permutations. I think there already is a ticket about this somewhere (or related to it), but I don't remember the number off hand.
Best,
Travis
comment:24 Changed 8 years ago by
I also deprecated the robinson_schensted()
method for permutations.
For patchbot:
Apply: trac_8392-check_permutation-ts.patch
comment:25 Changed 8 years ago by
Travis -
A couple quick comments on the documentation:
In the docstring for sage.combinat.rsk.RSK:
- In the first paragraph "as known as two-line..." should be "also known as two-line..." ?
-In your description of the algorithm p and q are first referenced as your insertion and recording tableaux and then they become P and Q in the next paragraph and in this paragraph p appears to be a generalized permutation.
In the docstring for sage.combinat.rsk.RSK_inverse:
- I think you forgot a colon at the end of the sentence beginning "Same for Edelman-Greene ..."
Haven't played with the functions yet (except for your examples), but plan to soon.
-Jeff
comment:26 Changed 8 years ago by
Hey Jeff,
Thanks for catching that. Fixed.
Best,
Travis
comment:27 Changed 8 years ago by
Travis,
Can you add some more checks for invalid input? For example there is no problem doing this:
sage: RSK([1],[1,2]) # Words are different length sage: RSK([2,1],[1,1]) # Not a generalized permutation
I am using the definition of generalized permutation in Stanley EC2 Chapter 7.
- Jeff
comment:28 Changed 8 years ago by
Hey Jeff,
I added the extra safety checks.
Best,
Travis
comment:29 Changed 8 years ago by
- Status changed from needs_review to positive_review
Looks good. It's going to be nice to have these functions around.
comment:30 Changed 8 years ago by
- Reviewers set to Jeff Ferreira, Darij Grinberg
Jeff, thanks for doing the final review. Darij thanks for doing the initial review.
comment:31 Changed 8 years ago by
Rebased to 5.10.beta4
(some fuzz).
For patchbot:
Apply: trac_8392-check_permutation-ts.patch
comment:32 Changed 8 years ago by
- Status changed from positive_review to needs_work
dochtml.log:[combinat ] /mazur/release/merger/sage-5.10.rc0/local/lib/python2.7/site-packages/sage/combinat/rsk.py:docstring of sage.combinat.rsk.RobinsonSchenstedKnuth:121: WARNING: Duplicate explicit target name: "knu1970". dochtml.log:[combinat ] /mazur/release/merger/sage-5.10.rc0/local/lib/python2.7/site-packages/sage/combinat/rsk.py:docstring of sage.combinat.rsk.RobinsonSchenstedKnuth:126: WARNING: Duplicate explicit target name: "eg1987". dochtml.log:[combinat ] /mazur/release/merger/sage-5.10.rc0/local/lib/python2.7/site-packages/sage/combinat/rsk.py:docstring of sage.combinat.rsk.RobinsonSchenstedKnuth:121: WARNING: duplicate citation Knu1970, other instance in /mazur/release/merger/sage-5.10.rc0/devel/sage/doc/en/reference/combinat/sage/combinat/rsk.rst dochtml.log:[combinat ] /mazur/release/merger/sage-5.10.rc0/local/lib/python2.7/site-packages/sage/combinat/rsk.py:docstring of sage.combinat.rsk.RobinsonSchenstedKnuth:126: WARNING: duplicate citation EG1987, other instance in /mazur/release/merger/sage-5.10.rc0/devel/sage/doc/en/reference/combinat/sage/combinat/rsk.rst
comment:33 Changed 8 years ago by
- Status changed from needs_work to positive_review
Fixed. Errors were due to references being in a function that had an alias.
comment:34 Changed 8 years ago by
- Milestone changed from sage-5.10 to sage-5.11
comment:35 Changed 8 years ago by
- Dependencies changed from #6495 #13605 #8703 #14459 #14319 to #6495, #13605, #8703, #14459, #14319, #14302
- Status changed from positive_review to needs_work
This needs to be rebased such that it applies on top of #14302.
comment:36 Changed 8 years ago by
- Status changed from needs_work to positive_review
Rebased over #14302.
comment:37 Changed 8 years ago by
- Merged in set to sage-5.11.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:38 follow-ups: ↓ 39 ↓ 41 Changed 8 years ago by
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.
comment:39 in reply to: ↑ 38 Changed 8 years ago by
I agree with Franco's comments!
Anne
comment:40 Changed 8 years ago by
- 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 toRSK_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)
comment:41 in reply to: ↑ 38 ; follow-up: ↓ 42 Changed 8 years ago by
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
comment:42 in reply to: ↑ 41 Changed 8 years ago by
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 methodRSK()
where each type of object implements it's own version of RSK andRSKUsable
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.<tab completion> 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
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: