Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#27852 closed enhancement (fixed)

Refactor structure of RSK

Reported by: gh-ChamanAgrawal Owned by:
Priority: major Milestone: sage-8.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:

Status badges

Description

To change the structure of rsk() function to follow a Rule-based framework.

Change History (67)

comment:1 Changed 3 years ago by gh-ChamanAgrawal

  • Type changed from PLEASE CHANGE to task

comment:2 Changed 3 years ago by gh-ChamanAgrawal

  • Branch set to u/gh-ChamanAgrawal/27852_refactorRSK
  • Commit set to b095c28ab1827955aa47b6db74e1cf50523f6807

New commits:

edbe8d0temperary changes
55a69cfImplemented Schensted forward_rule
b095c28WIP

comment:3 Changed 3 years ago by gh-ChamanAgrawal

@tscrim. WIP The current code is not working (Doc tests and all).

Last edited 3 years ago by gh-ChamanAgrawal (previous) (diff)

comment:4 Changed 3 years ago by git

  • Commit changed from b095c28ab1827955aa47b6db74e1cf50523f6807 to 87724298561e4410474c11174dce6fdbc9788e07

Branch pushed to git repo; I updated commit sha1. New commits:

8772429rules class working

comment:5 Changed 3 years ago by gh-ChamanAgrawal

  • Component changed from PLEASE CHANGE to combinatorics

comment:6 Changed 3 years ago by git

  • Commit changed from 87724298561e4410474c11174dce6fdbc9788e07 to 3810f356252e4fa834da86889bec2cdcc57311a6

Branch pushed to git repo; I updated commit sha1. New commits:

3810f35RSK started working for input as array and matrix

comment:7 Changed 3 years ago by git

  • Commit changed from 3810f356252e4fa834da86889bec2cdcc57311a6 to 9df7414f44d2c2b6a8846f9802caf2d814e9ddfb

Branch pushed to git repo; I updated commit sha1. New commits:

9df7414Implemented EG and Hecke algorithm

comment:8 Changed 3 years ago by git

  • Commit changed from 9df7414f44d2c2b6a8846f9802caf2d814e9ddfb to ddd5dc739aa6bfdc500f545196fa6625559b8dee

Branch pushed to git repo; I updated commit sha1. New commits:

ddd5dc7Implemented separate insertion for each algorithm

comment:9 Changed 3 years ago by git

  • Commit changed from ddd5dc739aa6bfdc500f545196fa6625559b8dee to 0df3c4a5cd032123b56accf2bc4746076b1660ff

Branch pushed to git repo; I updated commit sha1. New commits:

0df3c4aImproved insertion algorithms and changed documentation

comment:10 Changed 3 years ago by git

  • Commit changed from 0df3c4a5cd032123b56accf2bc4746076b1660ff to 1a1ece60c119972e2e113d14200ac5dd247d809d

Branch pushed to git repo; I updated commit sha1. New commits:

1a1ece6Improved Documentation

comment:11 Changed 3 years ago by git

  • Commit changed from 1a1ece60c119972e2e113d14200ac5dd247d809d to f2d20ae63b08762e13fc2659230f2b7fe7668a76

Branch pushed to git repo; I updated commit sha1. New commits:

f2d20aeRefactored code and improved documentation

comment:12 Changed 3 years ago by git

  • Commit changed from f2d20ae63b08762e13fc2659230f2b7fe7668a76 to 1796aa1d17679cd84b6e8de1b67fe65da166ebdc

Branch pushed to git repo; I updated commit sha1. New commits:

1796aa1Refactored forward rule and included seperate input-output parameter values for each rule in documentation

comment:13 Changed 3 years ago by git

  • Commit changed from 1796aa1d17679cd84b6e8de1b67fe65da166ebdc to f359ae2b3a486ce50859a1de458266deb357e8bd

Branch pushed to git repo; I updated commit sha1. New commits:

f359ae2moved forward_rule to the parent class

comment:14 Changed 3 years ago by git

  • Commit changed from f359ae2b3a486ce50859a1de458266deb357e8bd to 6fa8770bb00fe086db38828c3867d68e52eb78c6

Branch pushed to git repo; I updated commit sha1. New commits:

6fa8770Added rev_insertion method to refactor backward_rule

comment:15 Changed 3 years ago by git

  • Commit changed from 6fa8770bb00fe086db38828c3867d68e52eb78c6 to a29a391bc83cd49f387b538fa0abd6cc4d5b3091

Branch pushed to git repo; I updated commit sha1. New commits:

a29a391Added format_output method

comment:16 Changed 3 years ago by git

  • Commit changed from a29a391bc83cd49f387b538fa0abd6cc4d5b3091 to 13d6f995649a68d69972d0b9b1cd1bcb67e1b597

Branch pushed to git repo; I updated commit sha1. New commits:

13d6f99Implemented rev_insertion for non-standard q in EG insertion and refactored format_output()

comment:17 Changed 3 years ago by git

  • Commit changed from 13d6f995649a68d69972d0b9b1cd1bcb67e1b597 to 3491bb909cb302e3b902c4596ed9703064764d22

Branch pushed to git repo; I updated commit sha1. New commits:

3491bb9Updated Documentation

comment:18 Changed 3 years ago by git

  • Commit changed from 3491bb909cb302e3b902c4596ed9703064764d22 to 5b5b92fab694dc785b114b046011586c1ae077c3

Branch pushed to git repo; I updated commit sha1. New commits:

5b5b92fUpdated Documentation

comment:19 Changed 3 years ago by git

  • Commit changed from 5b5b92fab694dc785b114b046011586c1ae077c3 to 7eeb728c745af55e945a45d0923f26acc60fb23b

Branch pushed to git repo; I updated commit sha1. New commits:

7eeb728Updated Documentation and Doc Tests

comment:20 Changed 3 years ago by git

  • Commit changed from 7eeb728c745af55e945a45d0923f26acc60fb23b to ffcc27462a2e3006817460c8ea2206f3b159e09b

Branch pushed to git repo; I updated commit sha1. New commits:

ffcc274Refactored format Output for forward rule

comment:21 Changed 3 years ago by git

  • Commit changed from ffcc27462a2e3006817460c8ea2206f3b159e09b to 45869d911ca94ac2baaebd6c73986e0d6ef4d498

Branch pushed to git repo; I updated commit sha1. New commits:

45869d9Minor documentation changes

comment:22 Changed 3 years ago by git

  • Commit changed from 45869d911ca94ac2baaebd6c73986e0d6ef4d498 to cabc1ec163c1167c5b26c8ca1c125117eb52d782

Branch pushed to git repo; I updated commit sha1. New commits:

cabc1ecAdd one-line doc and examples to functions

comment:23 Changed 3 years ago by git

  • Commit changed from cabc1ec163c1167c5b26c8ca1c125117eb52d782 to 53ee04a7882afa4c63462516bd226cab1e143f35

Branch pushed to git repo; I updated commit sha1. New commits:

53ee04aAdd examples to functions

comment:24 Changed 3 years ago by git

  • Commit changed from 53ee04a7882afa4c63462516bd226cab1e143f35 to 37d09de5740b1eed47d3fd149ebef2c9b34cc4bb

Branch pushed to git repo; I updated commit sha1. New commits:

37d09deAdded simpler examples in RuleEG rev_insertion

comment:25 Changed 3 years ago by tscrim

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 row-by-row 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 module-level doc will only be looked at by the compiled documentation, so links will be sufficient.

Returns -> Return for 1-line 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 module-level. (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 git

  • Commit changed from 37d09de5740b1eed47d3fd149ebef2c9b34cc4bb to 5313c0e8b5bb1bc6649f9defa1e6d3c39745da6f

Branch pushed to git repo; I updated commit sha1. New commits:

5313c0eChanged (rev)insertion() to single row operation

comment:27 Changed 3 years ago by git

  • Commit changed from 5313c0e8b5bb1bc6649f9defa1e6d3c39745da6f to 734ae02079472057d8bd394b03c5e2edd0726d00

Branch pushed to git repo; I updated commit sha1. New commits:

734ae02Moved rules' documentation into their class

comment:28 Changed 3 years ago by tscrim

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 gh-ChamanAgrawal

  • Authors set to Chaman Agrawal
  • Status changed from new to needs_review

comment:30 Changed 3 years ago by git

  • Commit changed from 734ae02079472057d8bd394b03c5e2edd0726d00 to a21d65f875c76954a8b169c4efdb0d0d964d4535

Branch pushed to git repo; I updated commit sha1. New commits:

a21d65fChange insertion function

comment:31 Changed 3 years ago by git

  • Commit changed from a21d65f875c76954a8b169c4efdb0d0d964d4535 to d5bf7debd2d938a0d8e141f3bcab32145d3d4f73

Branch pushed to git repo; I updated commit sha1. New commits:

d5bf7deChange insertion() to reduce passing parameters

comment:32 Changed 3 years ago by tscrim

  • 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 singular tableau.
  • Remove all trailing whitespace.
  • In RuleEG, the TEST:: should be TESTS: and the text is overindented.
  • For insertion, you can just return None if the letter was added at the end (so you can drop the insertion_completed variable).
  • In forward_rule after the else:, 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 git

  • Commit changed from d5bf7debd2d938a0d8e141f3bcab32145d3d4f73 to 5cc0008640ffd3ded68d9c508d07f776d470d937

Branch pushed to git repo; I updated commit sha1. New commits:

5cc0008Minor changes in documentation

comment:34 Changed 3 years ago by git

  • Commit changed from 5cc0008640ffd3ded68d9c508d07f776d470d937 to 4ee1e3550add78cc8cee49ce0d6049b90d609c87

Branch pushed to git repo; I updated commit sha1. New commits:

4ee1e35Remove insertion_complete for insertion()

comment:35 Changed 3 years ago by git

  • Commit changed from 4ee1e3550add78cc8cee49ce0d6049b90d609c87 to f946493ef296141eff97b13d186dcb23da1de4e4

Branch pushed to git repo; I updated commit sha1. New commits:

f946493Add forgotten docs change

comment:36 Changed 3 years ago by tscrim

A few more trivial comments (from Darij):

The Robinson-Schensted-Knuth (RSK) correspondence is most naturally
-stated as a bijection between generalized permutation (also known
+stated as a bijection between generalized permutations (also known
as two-line arrays, biwords, ...) and pairs of semi-standard 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 git

  • Commit changed from f946493ef296141eff97b13d186dcb23da1de4e4 to e4554eebab17cb27c02e151c1e25566202e74d21

Branch pushed to git repo; I updated commit sha1. New commits:

e4554eeDocs corrected

comment:38 Changed 3 years ago by gh-darijgr

  • Branch changed from u/gh-ChamanAgrawal/27852_refactorRSK to public/ticket/27852
  • Commit changed from e4554eebab17cb27c02e151c1e25566202e74d21 to b6558c7078df4a4e445f04fbc7894b9230ed6c38

comment:39 Changed 3 years ago by git

  • Commit changed from b6558c7078df4a4e445f04fbc7894b9230ed6c38 to 6dba200348f75f2344952a2919d9acd2d1f98abb

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

6dba200some attempts at improvements -- doctest anyone?

comment:40 Changed 3 years ago by git

  • Commit changed from 6dba200348f75f2344952a2919d9acd2d1f98abb to 688dbf26f568c93774050c4c578206ebbded6e6d

Branch pushed to git repo; I updated commit sha1. New commits:

688dbf2corrections

comment:41 Changed 3 years ago by git

  • Commit changed from 688dbf26f568c93774050c4c578206ebbded6e6d to 59e414f3b7ca98387153221ec3af0a2a340520dd

Branch pushed to git repo; I updated commit sha1. New commits:

59e414fmore questionable fixes

comment:42 Changed 3 years ago by git

  • Commit changed from 59e414f3b7ca98387153221ec3af0a2a340520dd to c73eb09596bf34721a014012194263681150b37c

Branch pushed to git repo; I updated commit sha1. New commits:

c73eb09ooops

comment:43 Changed 3 years ago by git

  • Commit changed from c73eb09596bf34721a014012194263681150b37c to c373078c37eb46f51d743639d060a2b573b62df4

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c373078ooops

comment:44 Changed 3 years ago by git

  • Commit changed from c373078c37eb46f51d743639d060a2b573b62df4 to 46d4953bdc0eb6600cb38fe8fad012665d409fc5

Branch pushed to git repo; I updated commit sha1. New commits:

46d4953more

comment:45 Changed 3 years ago by git

  • Commit changed from 46d4953bdc0eb6600cb38fe8fad012665d409fc5 to b02351b5eddf4a46b8c31b75dde8745d2e7abcc1

Branch pushed to git repo; I updated commit sha1. New commits:

b02351bmore oops

comment:46 Changed 3 years ago by git

  • Commit changed from b02351b5eddf4a46b8c31b75dde8745d2e7abcc1 to 6fa17ea6feea89e283ec3871f65c93024ddb4d3b

Branch pushed to git repo; I updated commit sha1. New commits:

6fa17eamore

comment:47 Changed 3 years ago by git

  • Commit changed from 6fa17ea6feea89e283ec3871f65c93024ddb4d3b to 4dfa3e20df70a60e904be92071c7db309cb6f89e

Branch pushed to git repo; I updated commit sha1. New commits:

4dfa3e2this?

comment:48 Changed 3 years ago by git

  • Commit changed from 4dfa3e20df70a60e904be92071c7db309cb6f89e to c529820bf3fa54b494855f98856748840e8ac562

Branch pushed to git repo; I updated commit sha1. New commits:

c529820better?

comment:49 Changed 3 years ago by git

  • Commit changed from c529820bf3fa54b494855f98856748840e8ac562 to c523705abd3da706f72d25c19a554e18bf929dca

Branch pushed to git repo; I updated commit sha1. New commits:

c523705oo

comment:50 Changed 3 years ago by git

  • Commit changed from c523705abd3da706f72d25c19a554e18bf929dca to 2cdacd3fc508558535b0a9d95f8cc6ff6e83a380

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

2cdacd3oo

comment:51 Changed 3 years ago by git

  • Commit changed from 2cdacd3fc508558535b0a9d95f8cc6ff6e83a380 to faaf8ef2a1f93e20b735b949e61e1b3e9bf57bcb

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

faaf8efoo

comment:52 Changed 3 years ago by gh-darijgr

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 git

  • Commit changed from faaf8ef2a1f93e20b735b949e61e1b3e9bf57bcb to 81281cbc48f63d708456e3fadd6ce3769912e85e

Branch pushed to git repo; I updated commit sha1. New commits:

81281cbnow?

comment:54 Changed 3 years ago by git

  • Commit changed from 81281cbc48f63d708456e3fadd6ce3769912e85e to 8f72144219e1638c9834bea2e7c17ba585eb2db3

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8f72144now?

comment:55 Changed 3 years ago by git

  • Commit changed from 8f72144219e1638c9834bea2e7c17ba585eb2db3 to 9913530422809e98a5114045b95693fe02f1db63

Branch pushed to git repo; I updated commit sha1. New commits:

9913530more readable doc and less confusing method name

comment:56 Changed 3 years ago by git

  • Commit changed from 9913530422809e98a5114045b95693fe02f1db63 to dd90e957596e70aa13b8808a36a49f545f4a4ff8

Branch pushed to git repo; I updated commit sha1. New commits:

5a0b3ffprolly not
dd90e95and now?

comment:57 Changed 3 years ago by git

  • Commit changed from dd90e957596e70aa13b8808a36a49f545f4a4ff8 to d8e3ac9edc1c30489f66f2997d9dd04f8434185a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d8e3ac9review, take 1

comment:58 Changed 3 years ago by git

  • Commit changed from d8e3ac9edc1c30489f66f2997d9dd04f8434185a to 2d33d255be2339649c75542cc29cc5ea1aba2526

Branch pushed to git repo; I updated commit sha1. New commits:

72d09e2Removing default arguments for *_format_output because they should always be given.
218388eBringing back the permutation output for reverse EG insertion.
2d33d25Some last little details.

comment:59 Changed 3 years ago by git

  • Commit changed from 2d33d255be2339649c75542cc29cc5ea1aba2526 to 2162166e1725b15855228544f8f5d8faf4e80254

Branch pushed to git repo; I updated commit sha1. New commits:

2162166clarify some doc

comment:60 Changed 3 years ago by gh-darijgr

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 gh-darijgr

  • Reviewers set to Travis Scrimshaw, Anne Schilling, Darij Grinberg

comment:62 Changed 3 years ago by tscrim

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 git

  • Commit changed from 2162166e1725b15855228544f8f5d8faf4e80254 to 581ae30c3441f302569a0b934994434a8e83d1c7

Branch pushed to git repo; I updated commit sha1. New commits:

581ae30more Edelman-Greene doc fixes

comment:64 Changed 3 years ago by tscrim

  • Milestone changed from sage-feature to sage-8.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 tscrim

  • Keywords fpsac2019 added

comment:66 Changed 3 years ago by vbraun

  • 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 aschilling

  • Cc aschilling added
  • Commit 581ae30c3441f302569a0b934994434a8e83d1c7 deleted
Note: See TracTickets for help on using tickets.