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

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