I want to code the Robinson-Schensted correspondence in MatLab.

3 次查看（过去 30 天）
badscience
badscience 2019-2-26
编辑： badscience 2019-2-26
I want to code the RSK algorithm in MatLab but dont know how to do so. For a given permutation of n integers where every integer from 1 to n is present in the permutation, I need to write an algorithm that will generate two different arrays following the Robinson-Schensted correspondence. It has been coded in python here https://mathoverflow.net/questions/30910/implementation-of-the-robinson-schensted-correspondence and also a few other languages but I have not been able to sucessfully code this in MatLab! My attempts all seem to be falling flat and not doing at all what I want them to do. Can anyone help?
  2 个评论
Geoff Hayes
Geoff Hayes 2019-2-26
badscience - please post the code that you have written and discuss what problems you are observing. Include any input parameters and show how you are calling your function or script.
badscience
badscience 2019-2-26
编辑：badscience 2019-2-26
Sorry my code is messy and I may have some unnecessay stuff, I am still learning! Please note here that some of the lines are unnecessary for this particular script and are just sort of there from attempts at different methods.
perm=input('Type permutation in vector of form [a b ... n]\n'); %this can be any permutation of the integers from 1 to n
n=length(perm);
P=zeros(n); % Set up the upper bounds on the dimensions of the output matricies
Q=zeros(n); % I am trying to just modiy these matricies as I go
index=1;
P(1,1)=perm(1);
M{1}=P;
Q(1,1)=index;
i=1;
for i=2:n
[row, column]=find(P==perm(i-1));
maxperm=max(max(P));
if perm(i)>maxperm
P=[P perm(i)]; %Appends the larger value (i hope)
sort(P); % Hopefully puts the rows back in increasing order if anything went wrong.
elseif perm(i)<maxperm
%THIS IS WHERE I DONT KNOW WHAT TO DO. If the next entry bigger than any in the
%row, it can just be appended on the end of the first row. If not, it needs to
%take the place of the next larger integer in that row, bumping that integer
%down to the next row where it has to be checked against the second row and so on
end
end
P
Q
So I am having trouble figuring out how to "bump" numbers down to a lower row. Just as an example, this is what the algorithm needs to do if, say, the permutation was [4 3 5 1 2]:
Step one: P will be a 5x5 matrix of zeros
P = 0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Then, 4 is inserted into the top left
P = 4 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
The next entry is 3, since 3<4, 3 takes the place of 4 and 4 is bumped to the next row:
P = 3 0 0 0 0
4 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
The next entry is 5, since 5 is greater than anything in the first row, it is just appended on the end of the first row
P = 3 5 0 0 0
4 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Then we have 1, Since 1<3<5, 1 takes the place of the 3, bumping the 3 down. But then since 3<4, 3 takes the place of 4, bumping 4 down
P = 1 5 0 0 0
3 0 0 0 0
4 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Then the last entry is 2. Since 1<2<5, 2 takes the place of 5 bumping it to the second row. There, since 5>3, 5 is just appended on the second row.
P = 1 2 0 0 0
3 5 0 0 0
4 0 0 0 0
0 0 0 0 0
0 0 0 0 0
That is the final P array that I should get. I will also need to create a cooresponding Q vector in accordance with RSK, but first things first.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Programming 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by