# HW 16
# Jike Liu

# All the work is based on  C16.txt



# Question1:

# FindEntry(Y,m): inputs a tableau Y and an entry m
# outputs [r,c] where Y[r][c]=m
FindEntry := proc(Y,m) local r,c;
    for r from 1 to nops(Y) do
        for c from 1 to nops(Y[r]) do
            if Y[r][c]=m then
                RETURN([r,c]);
            fi;
        od;
    od;
    error "Entry %1 not found", m;
end:


# RemoveCorner(Y,r): removes the last cell of row r from tableau Y
# (here r should be the row of a corner cell)
RemoveCorner := proc(Y,r) local k,newrow;
    k := nops(Y);

    if nops(Y[r])=1 then
        if k=1 then
            RETURN([]);
        elif r=1 then
            RETURN([op(2..k,Y)]);
        elif r=k then
            RETURN([op(1..k-1,Y)]);
        else
            RETURN([op(1..r-1,Y), op(r+1..k,Y)]);
        fi;
    else
        newrow := [op(1..nops(Y[r])-1, Y[r])];
        if r=1 then
            RETURN([newrow, op(2..k,Y)]);
        elif r=k then
            RETURN([op(1..k-1,Y), newrow]);
        else
            RETURN([op(1..r-1,Y), newrow, op(r+1..k,Y)]);
        fi;
    fi;
end:


# ReverseRS1(P,r): reverse row insertion from the corner at the end of row r
# inputs a tableau P and a row index r
# outputs [P1,x] where P1 is the smaller tableau and x is the ejected entry
ReverseRS1 := proc(P,r)
local x,s,j,row,bumped,newrow,k,P1;

    k := nops(P);

    # remove the corner entry from row r
    x := P[r][nops(P[r])];
    P1 := RemoveCorner(P,r);

    # if the corner was in the first row, we are done
    if r=1 then
        RETURN([P1,x]);
    fi;

    # now move upward through rows r-1, r-2, ..., 1
    for s from r-1 by -1 to 1 do
        row := P1[s];
        j := nops(row);

        # find the rightmost entry < x
        while row[j] >= x do
            j := j-1;
        od;

        bumped := row[j];
        newrow := [op(1..j-1,row), x, op(j+1..nops(row),row)];

        if s=1 then
            if nops(P1)=1 then
                P1 := [newrow];
            else
                P1 := [newrow, op(2..nops(P1),P1)];
            fi;
        elif s=nops(P1) then
            P1 := [op(1..s-1,P1), newrow];
        else
            P1 := [op(1..s-1,P1), newrow, op(s+1..nops(P1),P1)];
        fi;

        x := bumped;
    od;

    RETURN([P1,x]);
end:


# AntiRS(Pair): inputs Pair=[P,Q] in SYTpairs(n)
# outputs the permutation pi such that RS(pi)=Pair
AntiRS := proc(Pair)
local P,Q,n,k,pos,r,tmp,x,pi,i;

    P := Pair[1];
    Q := Pair[2];

    n := add(nops(P[i]), i=1..nops(P));
    pi := [];

    for k from n by -1 to 1 do
        pos := FindEntry(Q,k);
        r := pos[1];

        tmp := ReverseRS1(P,r);
        P := tmp[1];
        x := tmp[2];

        Q := RemoveCorner(Q,r);

        pi := [x, op(pi)];
    od;

    RETURN(pi);
end:

# Check: 

with(combinat):

# Check 1:
# {seq(evalb(AntiRS(RS(pi))=pi), pi in permute(n))} = {true}
for n from 2 to 7 do
    print(n,
          {seq(evalb(AntiRS(RS(pi)) = pi), pi in permute(n))});
od:

with(combinat):

for n from 2 to 7 do
    print(n,
          {seq(evalb(RS(AntiRS(s)) = s), s in SYTpairs(n))});
od:



# Question 2:

with(combinat):

# InvPerm(pi): inverse of a permutation pi
InvPerm := proc(pi)
local n, i, tau;
    n := nops(pi);
    for i from 1 to n do
        tau[pi[i]] := i;
    od;
    return [seq(tau[i], i=1..n)];
end:

# experimental verification up to n=7
for n from 1 to 7 do
    print(n,
          evalb(
            {seq(evalb(RS(InvPerm(pi)) = [RS(pi)[2], RS(pi)[1]]),
                 pi in permute(n))} = {true}
          )
    );
od:

# Unfortunately, I have not yet obtained a proof.



# End of the file.