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

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?

[Geoff Hayes]

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]

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.