#27852 closed enhancement (fixed)
Refactor structure of RSK
Reported by:  ghChamanAgrawal  Owned by:  

Priority:  major  Milestone:  sage8.9 
Component:  combinatorics  Keywords:  gsocRSK, fpsac2019 
Cc:  tscrim, darij, aschilling  Merged in:  
Authors:  Chaman Agrawal  Reviewers:  Travis Scrimshaw, Anne Schilling, Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  581ae30 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description
To change the structure of rsk() function to follow a Rulebased framework.
Change History (67)
comment:1 Changed 3 years ago by
 Type changed from PLEASE CHANGE to task
comment:2 Changed 3 years ago by
 Branch set to u/ghChamanAgrawal/27852_refactorRSK
 Commit set to b095c28ab1827955aa47b6db74e1cf50523f6807
comment:3 Changed 3 years ago by
@tscrim. WIP The current code is not working (Doc tests and all).
comment:4 Changed 3 years ago by
 Commit changed from b095c28ab1827955aa47b6db74e1cf50523f6807 to 87724298561e4410474c11174dce6fdbc9788e07
Branch pushed to git repo; I updated commit sha1. New commits:
8772429  rules class working

comment:5 Changed 3 years ago by
 Component changed from PLEASE CHANGE to combinatorics
comment:6 Changed 3 years ago by
 Commit changed from 87724298561e4410474c11174dce6fdbc9788e07 to 3810f356252e4fa834da86889bec2cdcc57311a6
Branch pushed to git repo; I updated commit sha1. New commits:
3810f35  RSK started working for input as array and matrix

comment:7 Changed 3 years ago by
 Commit changed from 3810f356252e4fa834da86889bec2cdcc57311a6 to 9df7414f44d2c2b6a8846f9802caf2d814e9ddfb
Branch pushed to git repo; I updated commit sha1. New commits:
9df7414  Implemented EG and Hecke algorithm

comment:8 Changed 3 years ago by
 Commit changed from 9df7414f44d2c2b6a8846f9802caf2d814e9ddfb to ddd5dc739aa6bfdc500f545196fa6625559b8dee
Branch pushed to git repo; I updated commit sha1. New commits:
ddd5dc7  Implemented separate insertion for each algorithm

comment:9 Changed 3 years ago by
 Commit changed from ddd5dc739aa6bfdc500f545196fa6625559b8dee to 0df3c4a5cd032123b56accf2bc4746076b1660ff
Branch pushed to git repo; I updated commit sha1. New commits:
0df3c4a  Improved insertion algorithms and changed documentation

comment:10 Changed 3 years ago by
 Commit changed from 0df3c4a5cd032123b56accf2bc4746076b1660ff to 1a1ece60c119972e2e113d14200ac5dd247d809d
Branch pushed to git repo; I updated commit sha1. New commits:
1a1ece6  Improved Documentation

comment:11 Changed 3 years ago by
 Commit changed from 1a1ece60c119972e2e113d14200ac5dd247d809d to f2d20ae63b08762e13fc2659230f2b7fe7668a76
Branch pushed to git repo; I updated commit sha1. New commits:
f2d20ae  Refactored code and improved documentation

comment:12 Changed 3 years ago by
 Commit changed from f2d20ae63b08762e13fc2659230f2b7fe7668a76 to 1796aa1d17679cd84b6e8de1b67fe65da166ebdc
Branch pushed to git repo; I updated commit sha1. New commits:
1796aa1  Refactored forward rule and included seperate inputoutput parameter values for each rule in documentation

comment:13 Changed 3 years ago by
 Commit changed from 1796aa1d17679cd84b6e8de1b67fe65da166ebdc to f359ae2b3a486ce50859a1de458266deb357e8bd
Branch pushed to git repo; I updated commit sha1. New commits:
f359ae2  moved forward_rule to the parent class

comment:14 Changed 3 years ago by
 Commit changed from f359ae2b3a486ce50859a1de458266deb357e8bd to 6fa8770bb00fe086db38828c3867d68e52eb78c6
Branch pushed to git repo; I updated commit sha1. New commits:
6fa8770  Added rev_insertion method to refactor backward_rule

comment:15 Changed 3 years ago by
 Commit changed from 6fa8770bb00fe086db38828c3867d68e52eb78c6 to a29a391bc83cd49f387b538fa0abd6cc4d5b3091
Branch pushed to git repo; I updated commit sha1. New commits:
a29a391  Added format_output method

comment:16 Changed 3 years ago by
 Commit changed from a29a391bc83cd49f387b538fa0abd6cc4d5b3091 to 13d6f995649a68d69972d0b9b1cd1bcb67e1b597
Branch pushed to git repo; I updated commit sha1. New commits:
13d6f99  Implemented rev_insertion for nonstandard q in EG insertion and refactored format_output()

comment:17 Changed 3 years ago by
 Commit changed from 13d6f995649a68d69972d0b9b1cd1bcb67e1b597 to 3491bb909cb302e3b902c4596ed9703064764d22
Branch pushed to git repo; I updated commit sha1. New commits:
3491bb9  Updated Documentation

comment:18 Changed 3 years ago by
 Commit changed from 3491bb909cb302e3b902c4596ed9703064764d22 to 5b5b92fab694dc785b114b046011586c1ae077c3
Branch pushed to git repo; I updated commit sha1. New commits:
5b5b92f  Updated Documentation

comment:19 Changed 3 years ago by
 Commit changed from 5b5b92fab694dc785b114b046011586c1ae077c3 to 7eeb728c745af55e945a45d0923f26acc60fb23b
Branch pushed to git repo; I updated commit sha1. New commits:
7eeb728  Updated Documentation and Doc Tests

comment:20 Changed 3 years ago by
 Commit changed from 7eeb728c745af55e945a45d0923f26acc60fb23b to ffcc27462a2e3006817460c8ea2206f3b159e09b
Branch pushed to git repo; I updated commit sha1. New commits:
ffcc274  Refactored format Output for forward rule

comment:21 Changed 3 years ago by
 Commit changed from ffcc27462a2e3006817460c8ea2206f3b159e09b to 45869d911ca94ac2baaebd6c73986e0d6ef4d498
Branch pushed to git repo; I updated commit sha1. New commits:
45869d9  Minor documentation changes

comment:22 Changed 3 years ago by
 Commit changed from 45869d911ca94ac2baaebd6c73986e0d6ef4d498 to cabc1ec163c1167c5b26c8ca1c125117eb52d782
Branch pushed to git repo; I updated commit sha1. New commits:
cabc1ec  Add oneline doc and examples to functions

comment:23 Changed 3 years ago by
 Commit changed from cabc1ec163c1167c5b26c8ca1c125117eb52d782 to 53ee04a7882afa4c63462516bd226cab1e143f35
Branch pushed to git repo; I updated commit sha1. New commits:
53ee04a  Add examples to functions

comment:24 Changed 3 years ago by
 Commit changed from 53ee04a7882afa4c63462516bd226cab1e143f35 to 37d09de5740b1eed47d3fd149ebef2c9b34cc4bb
Branch pushed to git repo; I updated commit sha1. New commits:
37d09de  Added simpler examples in RuleEG rev_insertion

comment:25 Changed 3 years ago by
Here are my comments on the current version:
The insertion
and rev(erse)_insertion
should be doing the insertion on a specific row, and going rowbyrow should be done in the forward_rule
and backwards_rule
. Look at the amount of common code between the RSK and EG rules.
I prefer the original here:
We can perform RSK and the inverse on a variety of objects:: +We can perform RSK and the RSK_inverse on a variety of objects::
type`A`
> type `A`
I think we should move all of the information about the different types of insertions to their respective rule class docs. It is better locality and the RSK modulelevel doc will only be looked at by the compiled documentation, so links will be sufficient.
Returns
> Return
for 1line docs (e.g., in to_pair
). Similarly Inserts
> Insert
.
to_pair
does not need to return a list
from what I see.
For INPUT:
items, they do not start with a capital letter by convention, e.g.
  ``check_standard``  (Default: ``False``) Check if either of the +  ``check_standard``  (default: ``False``) check if either of the
Comments should be followed by at least one space.
I would move the import
from _forward_formatOutput
to the modulelevel. (Or does this cause an import cycle?) Same for the import of from bisect import bisect_left
.
_*_formatOuput
> _*_format_output
.
You should have the doc lines at most 80 chars/line (unless there is a really good reason to do so).
rev_insertion
> reverse_insertion
Examples::
> EXAMPLES::
I would just call p_copy
p
in rev(erse)_insertion
.
For precise information about I/O constrains, see the particular Rule class. +For precise information about constraints on the input and +output, see the particular :class:`~sage.combinat.rsk.Rule` class.
comment:26 Changed 3 years ago by
 Commit changed from 37d09de5740b1eed47d3fd149ebef2c9b34cc4bb to 5313c0e8b5bb1bc6649f9defa1e6d3c39745da6f
Branch pushed to git repo; I updated commit sha1. New commits:
5313c0e  Changed (rev)insertion() to single row operation

comment:27 Changed 3 years ago by
 Commit changed from 5313c0e8b5bb1bc6649f9defa1e6d3c39745da6f to 734ae02079472057d8bd394b03c5e2edd0726d00
Branch pushed to git repo; I updated commit sha1. New commits:
734ae02  Moved rules' documentation into their class

comment:28 Changed 3 years ago by
This is looking much better. A few more comments:
Change:
 r = [j]; p.append(r)  qr = [i]; q.append(qr) + p.append([j]) + q.append([i])
d = dict((qij,i) for i, Li in enumerate(q) for qij in Li) +d = {qij: i for i, Li in enumerate(q) for qij in Li}
I don't think the insertion
needs to take the qr
as you can have it have a True/False
return value which then is handled by the forward_rule
function (you always add to the end of the row).
I might have a few more additional comments, but this is all I have time right now to look at. However, you should now set this to needs review and put your real name as the author.
comment:29 Changed 3 years ago by
 Status changed from new to needs_review
comment:30 Changed 3 years ago by
 Commit changed from 734ae02079472057d8bd394b03c5e2edd0726d00 to a21d65f875c76954a8b169c4efdb0d0d964d4535
Branch pushed to git repo; I updated commit sha1. New commits:
a21d65f  Change insertion function

comment:31 Changed 3 years ago by
 Commit changed from a21d65f875c76954a8b169c4efdb0d0d964d4535 to d5bf7debd2d938a0d8e141f3bcab32145d3d4f73
Branch pushed to git repo; I updated commit sha1. New commits:
d5bf7de  Change insertion() to reduce passing parameters

comment:32 Changed 3 years ago by
 Cc darij added
A few last little small details:
 For the
INPUT:
blocks, do not start bullet points with a capital letter.  Remove the blank line before the closing
"""
in the docstrings (personal idiosyncrasy, but I think it looks better without it).  Space after the
#
for comments (this is a PEP8 thing).  In
the current insertion tableaux
, it should be the singulartableau
.  Remove all trailing whitespace.
 In
RuleEG
, theTEST::
should beTESTS:
and the text is overindented.  For
insertion
, you can just returnNone
if the letter was added at the end (so you can drop theinsertion_completed
variable).  In
forward_rule
after theelse:
, indent the comments one step (i.e., 4 spaces).
Darij, I put you in cc in case you had any comments.
comment:33 Changed 3 years ago by
 Commit changed from d5bf7debd2d938a0d8e141f3bcab32145d3d4f73 to 5cc0008640ffd3ded68d9c508d07f776d470d937
Branch pushed to git repo; I updated commit sha1. New commits:
5cc0008  Minor changes in documentation

comment:34 Changed 3 years ago by
 Commit changed from 5cc0008640ffd3ded68d9c508d07f776d470d937 to 4ee1e3550add78cc8cee49ce0d6049b90d609c87
Branch pushed to git repo; I updated commit sha1. New commits:
4ee1e35  Remove insertion_complete for insertion()

comment:35 Changed 3 years ago by
 Commit changed from 4ee1e3550add78cc8cee49ce0d6049b90d609c87 to f946493ef296141eff97b13d186dcb23da1de4e4
Branch pushed to git repo; I updated commit sha1. New commits:
f946493  Add forgotten docs change

comment:36 Changed 3 years ago by
A few more trivial comments (from Darij):
The RobinsonSchenstedKnuth (RSK) correspondence is most naturally stated as a bijection between generalized permutation (also known +stated as a bijection between generalized permutations (also known as twoline arrays, biwords, ...) and pairs of semistandard Young
implemented for the RSK correspondence which can be specify in +implemented for the RSK correspondence which can be specified in
comment:37 Changed 3 years ago by
 Commit changed from f946493ef296141eff97b13d186dcb23da1de4e4 to e4554eebab17cb27c02e151c1e25566202e74d21
Branch pushed to git repo; I updated commit sha1. New commits:
e4554ee  Docs corrected

comment:38 Changed 3 years ago by
 Branch changed from u/ghChamanAgrawal/27852_refactorRSK to public/ticket/27852
 Commit changed from e4554eebab17cb27c02e151c1e25566202e74d21 to b6558c7078df4a4e445f04fbc7894b9230ed6c38
comment:39 Changed 3 years ago by
 Commit changed from b6558c7078df4a4e445f04fbc7894b9230ed6c38 to 6dba200348f75f2344952a2919d9acd2d1f98abb
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
6dba200  some attempts at improvements  doctest anyone?

comment:40 Changed 3 years ago by
 Commit changed from 6dba200348f75f2344952a2919d9acd2d1f98abb to 688dbf26f568c93774050c4c578206ebbded6e6d
Branch pushed to git repo; I updated commit sha1. New commits:
688dbf2  corrections

comment:41 Changed 3 years ago by
 Commit changed from 688dbf26f568c93774050c4c578206ebbded6e6d to 59e414f3b7ca98387153221ec3af0a2a340520dd
Branch pushed to git repo; I updated commit sha1. New commits:
59e414f  more questionable fixes

comment:42 Changed 3 years ago by
 Commit changed from 59e414f3b7ca98387153221ec3af0a2a340520dd to c73eb09596bf34721a014012194263681150b37c
Branch pushed to git repo; I updated commit sha1. New commits:
c73eb09  ooops

comment:43 Changed 3 years ago by
 Commit changed from c73eb09596bf34721a014012194263681150b37c to c373078c37eb46f51d743639d060a2b573b62df4
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c373078  ooops

comment:44 Changed 3 years ago by
 Commit changed from c373078c37eb46f51d743639d060a2b573b62df4 to 46d4953bdc0eb6600cb38fe8fad012665d409fc5
Branch pushed to git repo; I updated commit sha1. New commits:
46d4953  more

comment:45 Changed 3 years ago by
 Commit changed from 46d4953bdc0eb6600cb38fe8fad012665d409fc5 to b02351b5eddf4a46b8c31b75dde8745d2e7abcc1
Branch pushed to git repo; I updated commit sha1. New commits:
b02351b  more oops

comment:46 Changed 3 years ago by
 Commit changed from b02351b5eddf4a46b8c31b75dde8745d2e7abcc1 to 6fa17ea6feea89e283ec3871f65c93024ddb4d3b
Branch pushed to git repo; I updated commit sha1. New commits:
6fa17ea  more

comment:47 Changed 3 years ago by
 Commit changed from 6fa17ea6feea89e283ec3871f65c93024ddb4d3b to 4dfa3e20df70a60e904be92071c7db309cb6f89e
Branch pushed to git repo; I updated commit sha1. New commits:
4dfa3e2  this?

comment:48 Changed 3 years ago by
 Commit changed from 4dfa3e20df70a60e904be92071c7db309cb6f89e to c529820bf3fa54b494855f98856748840e8ac562
Branch pushed to git repo; I updated commit sha1. New commits:
c529820  better?

comment:49 Changed 3 years ago by
 Commit changed from c529820bf3fa54b494855f98856748840e8ac562 to c523705abd3da706f72d25c19a554e18bf929dca
Branch pushed to git repo; I updated commit sha1. New commits:
c523705  oo

comment:50 Changed 3 years ago by
 Commit changed from c523705abd3da706f72d25c19a554e18bf929dca to 2cdacd3fc508558535b0a9d95f8cc6ff6e83a380
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
2cdacd3  oo

comment:51 Changed 3 years ago by
 Commit changed from 2cdacd3fc508558535b0a9d95f8cc6ff6e83a380 to faaf8ef2a1f93e20b735b949e61e1b3e9bf57bcb
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
faaf8ef  oo

comment:52 Changed 3 years ago by
Construction zone  some functionality (reverse EG output as permutation) removed for now since I don't understand it and the tests are broken. We will perhaps want to reintroduce it after reviewing the rest.
comment:53 Changed 3 years ago by
 Commit changed from faaf8ef2a1f93e20b735b949e61e1b3e9bf57bcb to 81281cbc48f63d708456e3fadd6ce3769912e85e
Branch pushed to git repo; I updated commit sha1. New commits:
81281cb  now?

comment:54 Changed 3 years ago by
 Commit changed from 81281cbc48f63d708456e3fadd6ce3769912e85e to 8f72144219e1638c9834bea2e7c17ba585eb2db3
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
8f72144  now?

comment:55 Changed 3 years ago by
 Commit changed from 8f72144219e1638c9834bea2e7c17ba585eb2db3 to 9913530422809e98a5114045b95693fe02f1db63
Branch pushed to git repo; I updated commit sha1. New commits:
9913530  more readable doc and less confusing method name

comment:56 Changed 3 years ago by
 Commit changed from 9913530422809e98a5114045b95693fe02f1db63 to dd90e957596e70aa13b8808a36a49f545f4a4ff8
comment:57 Changed 3 years ago by
 Commit changed from dd90e957596e70aa13b8808a36a49f545f4a4ff8 to d8e3ac9edc1c30489f66f2997d9dd04f8434185a
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
d8e3ac9  review, take 1

comment:58 Changed 3 years ago by
 Commit changed from d8e3ac9edc1c30489f66f2997d9dd04f8434185a to 2d33d255be2339649c75542cc29cc5ea1aba2526
comment:59 Changed 3 years ago by
 Commit changed from 2d33d255be2339649c75542cc29cc5ea1aba2526 to 2162166e1725b15855228544f8f5d8faf4e80254
Branch pushed to git repo; I updated commit sha1. New commits:
2162166  clarify some doc

comment:60 Changed 3 years ago by
This looks good, with one exception: The permutation output for reverse EG is neither doced nor (explicitly) doctested; it's almost an easter egg...
comment:61 Changed 3 years ago by
 Reviewers set to Travis Scrimshaw, Anne Schilling, Darij Grinberg
comment:62 Changed 3 years ago by
There is an explicit test in RuleEG
for the permutation output (it is the last test in that docstring) and the permutation output doc is inherited from Rule.backward_rule()
. So they are there.
Also, I forgot to make this change on my push:
for RSK() and RSK_inverse() respectively (as methods +for :func:`RSK()` and :func:`RSK_inverse()` respectively (as methods
comment:63 Changed 3 years ago by
 Commit changed from 2162166e1725b15855228544f8f5d8faf4e80254 to 581ae30c3441f302569a0b934994434a8e83d1c7
Branch pushed to git repo; I updated commit sha1. New commits:
581ae30  more EdelmanGreene doc fixes

comment:64 Changed 3 years ago by
 Milestone changed from sagefeature to sage8.9
 Status changed from needs_review to positive_review
 Type changed from task to enhancement
Thank you for the help with the review Darij.
comment:65 Changed 3 years ago by
 Keywords fpsac2019 added
comment:66 Changed 3 years ago by
 Branch changed from public/ticket/27852 to 581ae30c3441f302569a0b934994434a8e83d1c7
 Resolution set to fixed
 Status changed from positive_review to closed
comment:67 Changed 3 years ago by
 Cc aschilling added
 Commit 581ae30c3441f302569a0b934994434a8e83d1c7 deleted
New commits:
temperary changes
Implemented Schensted forward_rule
WIP