RSK correspondence in SAGE

SAGE has a function to perform Robinson-Schensted algorith on a permutation. However it lacks the Robinson-Schensted-Knuth generalization that gives the bijection between nonnegative integer matrices and pairs of semistandard Young tableau.

After waiting a long time hoping someone would implement it, I needed it to do some checks related to my thesis, so I took RS code and adapted it. Posting here so it won’t get lost.

from itertools import izip
from bisect import bisect
def RSK(M):
""" Implementation of the Robinson-Schensted-Knuth algorithm
for non negative integer matrices, based on the Robinson-Schensted implementation for Permutations

"""
# M is the matrix corresponding to the pair of tableau (P,Q)

# First we create the double-row array
upperrow = []
lowerrow = []
for r in range(M.nrows()):
fila = M[r]
for c in range(len(fila)):
for k in range(M[r][c]):
upperrow.append(r+1)
lowerrow.append(c+1)
p = []       #the "insertion" tableau
q = []       #the "recording" tableau

# We proceed to do bumping algorithm on lower row
# and recording places on upper row
for a,b in izip(upperrow, lowerrow):
for r,qr in izip(p,q):
if r[-1] > b:
y_pos = bisect(r,b)
b, r[y_pos] = r[y_pos], b
else:
break
else:
r=[]; p.append(r)
qr = []; q.append(qr)

r.append(b)
qr.append(a)
return [Tableau(p), Tableau(q)]


Example.

Perform the RSK correspondence on  matrix
$\begin{pmatrix} 1&0&2 \\ 0&2&0 \\ 1&1&0 \end{pmatrix}$

Me= Matrix( [[1,0,2],[0,2,0],[1,1,0]] )
RSK(Me)

[[[1, 1, 2, 2], [2, 3], [3]], [[1, 1, 1, 3], [2, 2], [3]]]


gives the pair of tableau
P:
 1 1 2 2 2 3 3 
and
Q:
 1 1 1 3 2 2 3 

Anuncios