Mixed Shifted Insertion.sagews

def draw_shifted_tableau(t):
    ShiftedPrimedTableau([[int(i) if i>0 else "%s'"%int(-i) for i in row] for row in t]).pp()

def mixed_insertion(I):
    P=[[]]
    Q=[[]]
    for j,i in enumerate(I):
        (P,row,col)=mixed_insertion_i(P,i)
        if len(Q)<=row:
            Q.append([j+1])
        else:
            Q[row].append(j+1)
    return(P,Q)

def inverse_mixed_insertion(Pi,Qi):
    out=[]
    n=len(flatten(Qi))
    P=list(map(list,Pi))
    Q=list(map(list,Qi))
    while Q!=[]:
        for i in range(len(Q)-1,-1,-1):
            for j in range(len(Q[i])-1,-1,-1):
                if Q[i][j]==n:
                    break
            if Q[i][j]==n:
                n=n-1
                del Q[i][j]
                if Q[-1]==[]:
                    del Q[-1]
                break
        cur=P[i][j]
        del P[i][j]
        P,cur=inverse_mixed_insertion_ij(P,cur,i,j+i)
        out+=[cur]
    return list(reversed(out))

def mixed_insertion_i(P,i):
    row=0
    col=0
    while i!=None:
        if i>0:
            (P,i,row,col)=insert_row(P,row,i)
        elif i<0:
            (P,i,row,col)=insert_column(P,col,i)
        if i!=None:
            if i>0:
                row+=1
                if len(P)<=row:
                    P+=[[]]
            elif i<0:
                col+=1
    return(P,row,col)

def inverse_mixed_insertion_ij(P,cur,i,j):
    while i>=0 and j>=0:
        if cur>0:
            P,cur,i,j=inverse_insert_row(P,cur,i,j)
        elif cur<0:
            P,cur,i,j=inverse_insert_column(P,cur,i,j)
    return(P,cur)

def insert_row(P,row,i):
    out=0
    k=0
    for k,j in enumerate(P[row]):
        if abs(j)>abs(i) or (abs(j)==abs(i) and i<0 and j>0):
            if k==0:
                out=-P[row][k]
            else:
                out=P[row][k]
            P[row][k]=i
            break
    if out==0:
        out=None
        P[row]+=[i]
    return (P,out,row,k+row)

def inverse_insert_row(P,cur,i,j):
    new=cur
    l=0
    if i>0:
        for l,k in reversed(list(enumerate(P[i-1]))):
            if abs(k)<abs(cur) or (abs(k)==abs(cur) and k<0 and cur>0):
                new=P[i-1][l]
                if l==0:
                    P[i-1][l]=abs(cur)
                else:
                    P[i-1][l]=cur
                break
    return(P,new,i-1,l+i-1)

def insert_column(P,col,i):
    out=0
    for k,r in enumerate(P):
        if len(r)>col-k and col-k>=0:
            j=P[k][col-k]
            if abs(j)>abs(i) or (abs(j)==abs(i) and i<0 and j>0):
                if col-k==0:
                    out=-P[k][col-k]
                else:
                    out=P[k][col-k]
                P[k][col-k]=i
                break
        else:
            break
    if out==0:
        out=None
        P[k]+=[i]
    return (P,out,k,col)

def inverse_insert_column(P,cur,i,j):
    new=cur
    l=0
    if j-i>0:
        for l,r in reversed(list(enumerate(P))):
            if len(r)>=j-l and j-l-1>=0:
                k=P[l][j-l-1]
                if abs(k)<abs(cur) or (abs(k)==abs(cur) and k<0 and cur>0):
                    new=P[l][j-l-1]
                    if j-l-1==0:
                        P[l][j-l-1]=abs(cur)
                    else:
                        P[l][j-l-1]=cur
                    break
    return(P,new,l,j-1)

def shjdt(T,row,col):
    while len(T)>=row or len(T[row])>=col-row:
        c=T[row][col-row]
        try:
            a=T[row+1][col-row-1]
        except:
            a=oo
        try:
            b=T[row][col+1-row]
        except:
            b=oo
        if c>a or c>b:
            if a>b:
                T[row][col-row]=b
                T[row][col+1-row]=c
                col=col+1
            else:
                T[row][col-row]=a
                T[row+1][col-row-1]=c
                row=row+1
        else:
            break
    return T
def Fischer_standardize(tab):
    out=tab
    for i in range(len(tab)-1,-1,-1):
        for j in range(len(tab[i])-1,-1,-1):
            out=shjdt(out,i,j+i)
    return out
def generate_random_shSYT(shape):
    w=Permutations(range(1,sum(shape)+1)).random_element()
    return(Fischer_standardize([w[sum(shape[:i]):sum(shape[:i+1])] for i in range(len(shape))]))
def generate_random_shMarkedSYT(shape):
    out=generate_random_shSYT(shape)
    for i in range(len(out)):
        for j in range(1,len(out[i])):
            out[i][j]=(-1)^ZZ.random_element(0,2)*out[i][j]
    return out
def minimal_skew(n,a,b):
    return mixed_insertion(flatten([[n-i for j in range(n-i-a)] if i<b else [n-i for j in range(n-i)] for i in range(n)]))[1]

#empirically test Fischer's standardization method
d={}
shape=[4,2,1]
n=sum(shape)
for w in Permutations(n):
    s=tuple(map(tuple,Fischer_standardize([w[sum(shape[:i]):sum(shape[:i+1])] for i in range(len(shape))])))
    if s not in d:
        d[s]=1
    else:
        d[s]+=1
d

{((1, 2, 3, 4), (5, 6), (7,)): 720, ((1, 2, 3, 5), (4, 6), (7,)): 720, ((1, 2, 3, 6), (4, 5), (7,)): 720, ((1, 2, 3, 7), (4, 5), (6,)): 720, ((1, 2, 4, 5), (3, 6), (7,)): 720, ((1, 2, 4, 6), (3, 5), (7,)): 720, ((1, 2, 4, 7), (3, 5), (6,)): 720}

#randomly generate some shifted marked tableaux
T=[tuple(map(tuple,generate_random_shMarkedSYT([3,1]))) for i in range(1000)]
[T.count(i) for i in Set(T)]

[139, 105, 126, 122, 117, 130, 136, 125]

#what the Q tableau looks like (the one we need to reverse insert)
ShiftedPrimedTableau(minimal_skew(20,9,4)).pp()

1 2 3 4 5 6 7 8 9 10 11 46 47 48 49 50 51 52 53 54 12 13 14 15 16 17 18 19 20 21 61 62 63 64 65 66 67 68 69 22 23 24 25 26 27 28 29 30 75 76 77 78 79 80 81 82 83 31 32 33 34 35 36 37 38 88 89 90 91 92 93 94 95 96 39 40 41 42 43 44 45 100 101 102 103 104 105 106 107 108 55 56 57 58 59 60 111 112 113 114 115 116 117 118 119 70 71 72 73 74 121 122 123 124 125 126 127 128 129 84 85 86 87 130 131 132 133 134 135 136 137 138 97 98 99 139 140 141 142 143 144 145 146 109 110 147 148 149 150 151 152 153 120 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

#generate S a random shifted marked standard tableau and T the corresponding skew standard tableau
n=50
a=15
b=20
Q=minimal_skew(n,a,b)
shape=list(map(len,Q))
N=sum(shape)
S=generate_random_shMarkedSYT(shape)
out=inverse_mixed_insertion(S,Q)
out=[N+1-j for j in out]
tri=list(range(n,0,-1))
T=[([None]*a +list(reversed([j for j in out[sum(tri[:i])-a*i:sum(tri[:i+1])-a*(i+1)]]))) if i<b else list(reversed([j for j in out[sum(tri[:i])-a*b:sum(tri[:i+1])-a*b]])) for i in range(n)]
#T

bands=3
graphics=polygon((0,0))
for i in range(len(T)):
    for j in range(len(T[i])):
        if T[i][j]==None:
            pass
        else:
            r = floor(bands*(T[i][j]-1)/(N))/bands
            graphics+=polygon([(i,-j),(i+1,-j),(i+1,-j-1),(i,-j-1)],rgbcolor=(r,r,r),edgecolor=Color(r,r,r),axes=False)
show(graphics)

graphics=polygon((0,0))
for i in range(len(S)):
    for j in range(len(S[i])):
        r = floor(bands*(abs(S[i][j])-1)/(N))/bands
        graphics+=polygon([(j+i,-i),(j+i,-i-1),(j+i+1,-i-1),(j+i+1,-i)],rgbcolor=(r,r,r),edgecolor=Color(r,r,r),axes=False)
show(graphics)

draw_shifted_tableau(S)
SemistandardSkewTableaux()(T).pp()

1 2 3 6 9 11 12 20 23 25 28 33' 42 53 55 71 4 5 8' 13 17' 19' 24 30 34 37 45 51 60' 69' 77' 7 10 14' 18' 21 27' 32' 36' 40' 49' 57 61 73 15 16' 26 29 38 39' 43 56' 62 67 70' 22 31' 35 41 44' 58' 66' 72 79 46 47 50' 54 64' 68' 74' 48 52 63' 65' 76 59 75 80 78 . . . . . . . 3 4 11 12 25 32 45 48 80 . . . . . . . 6 7 15 21 37 41 64 77 . . . . . . . 13 17 23 54 62 67 76 . . . . . . . 16 31 35 59 73 79 . . . . . . . 18 42 55 71 74 . . . . . . . 33 49 63 72 . . . . . . . 46 52 70 . . . . . . . 50 65 1 5 19 22 29 38 40 51 2 9 24 27 34 57 60 8 14 30 47 61 75 10 28 36 56 66 20 43 58 68 26 44 69 39 53 78

#run the bijection on standard skew tableaux
n=3
a=2
b=1
N=int(n*(n+1)/2-a*b)
#N
A=[a for a in SemistandardSkewTableaux([list(range(n,0,-1)),[a]*b],[1]*N)]#staircase,skew rectangle shape,content=all ones for standard, remove for all semistandard
for a in A:
    print(a,mixed_insertion([N-i for i in list(reversed(a.to_word_by_row().to_integer_list()))])[0])

4 [[None, None, 4], [1, 3], [2]] [[1, 2, 3], [4]] [[None, None, 4], [1, 2], [3]] [[1, 2, 4], [3]] [[None, None, 3], [1, 4], [2]] [[1, -2, 3], [4]] [[None, None, 2], [1, 4], [3]] [[1, 2, -3], [4]] [[None, None, 1], [2, 4], [3]] [[1, 2, -4], [3]] [[None, None, 3], [1, 2], [4]] [[1, -2, 4], [3]] [[None, None, 2], [1, 3], [4]] [[1, -2, -3], [4]] [[None, None, 1], [2, 3], [4]] [[1, -2, -4], [3]]

#run the bijection on semistandard skew tableaux
n=3
a=2
b=1
max_ent=3
A=[a for a in SemistandardSkewTableaux([list(range(n,0,-1)),[a]*b],max_entry=max_ent)]#staircase,skew rectangle shape,max_entry
out=[]
for a in A:
    word_a=[4-i for i in list(reversed(list(a.to_word_by_row())))]
    out+=[tuple(map(tuple,mixed_insertion(word_a)[0]))]
    print(a,out[-1])
len(out)
len(list(Set(out)))

[[None, None, 1], [1, 1], [2]] ((2, -3, 3), (3,)) [[None, None, 1], [1, 1], [3]] ((1, -3, 3), (3,)) [[None, None, 2], [1, 1], [2]] ((2, 2, 3), (3,)) [[None, None, 1], [1, 2], [2]] ((2, 2, -3), (3,)) [[None, None, 3], [1, 1], [2]] ((1, 2, 3), (3,)) [[None, None, 1], [1, 3], [2]] ((1, 2, -3), (3,)) [[None, None, 2], [1, 1], [3]] ((1, -2, 3), (3,)) [[None, None, 1], [1, 2], [3]] ((1, -2, -3), (3,)) [[None, None, 3], [1, 1], [3]] ((1, 1, 3), (3,)) [[None, None, 1], [1, 3], [3]] ((1, 1, -3), (3,)) [[None, None, 2], [1, 2], [2]] ((2, 2, 2), (3,)) [[None, None, 3], [1, 2], [2]] ((1, 2, 2), (3,)) [[None, None, 2], [1, 3], [2]] ((1, -2, 2), (3,)) [[None, None, 2], [1, 2], [3]] ((1, -2, 3), (2,)) [[None, None, 1], [2, 2], [3]] ((1, -2, -3), (2,)) [[None, None, 3], [1, 3], [2]] ((1, 1, 2), (3,)) [[None, None, 3], [1, 2], [3]] ((1, 1, 3), (2,)) [[None, None, 2], [1, 3], [3]] ((1, 1, -2), (3,)) [[None, None, 1], [2, 3], [3]] ((1, 1, -3), (2,)) [[None, None, 3], [1, 3], [3]] ((1, 1, 1), (3,)) [[None, None, 2], [2, 2], [3]] ((1, -2, 2), (2,)) [[None, None, 3], [2, 2], [3]] ((1, 1, 2), (2,)) [[None, None, 2], [2, 3], [3]] ((1, 1, -2), (2,)) [[None, None, 3], [2, 3], [3]] ((1, 1, 1), (2,)) 24 24

#run the bijection backwards on semistandard shifted marked tableaux
A=[[[i.integer() if i.is_unprimed() else -i.integer() for i in row] for row in list(a)] for a in ShiftedPrimedTableaux([3,1],max_entry=3)]
out=[]
for a in A:
    out+=[inverse_mixed_insertion(a,minimal_skew(3,2,1))]
    print(a,out[-1])
len(out)
len(list(Set(out)))

[[1, 1, 1], [2]] [1, 1, 2, 1] [[1, 1, 2], [2]] [1, 2, 2, 1] [[1, 1, -2], [2]] [2, 1, 2, 1] [[1, 1, 3], [2]] [1, 2, 3, 1] [[1, 1, -3], [2]] [3, 1, 2, 1] [[1, 1, 2], [3]] [1, 1, 3, 2] [[1, 1, -2], [3]] [2, 1, 3, 1] [[1, 1, 1], [3]] [1, 1, 3, 1] [[1, -2, 2], [2]] [2, 2, 2, 1] [[1, -2, 3], [2]] [2, 2, 3, 1] [[1, 1, 3], [3]] [1, 3, 3, 1] [[1, -2, -3], [2]] [3, 2, 2, 1] [[1, 2, 2], [3]] [1, 2, 3, 2] [[1, -2, 2], [3]] [2, 1, 3, 2] [[1, 1, -3], [3]] [3, 1, 3, 1] [[1, -2, 3], [3]] [2, 3, 3, 1] [[1, 2, 3], [3]] [1, 3, 3, 2] [[1, -2, -3], [3]] [3, 2, 3, 1] [[2, 2, 2], [3]] [2, 2, 3, 2] [[1, 2, -3], [3]] [3, 1, 3, 2] [[1, -3, 3], [3]] [3, 3, 3, 1] [[2, 2, 3], [3]] [2, 3, 3, 2] [[2, 2, -3], [3]] [3, 2, 3, 2] [[2, -3, 3], [3]] [3, 3, 3, 2] 24 24