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)]
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], ], [[1, 1, 1, 3], [2, 2], ]]
gives the pair of tableau
1 1 2 2
1 1 1 3