Could someone be kind enough to point me in the right direction to
polish and submit a new sage function?
SAGE already has an implementation of the Robinson-Schensted algorithm
for permutations (bijection between permutations and standard Young
tableaux),
which I used as a base to implement the Robinson-Schensted-Knuth
generalization (bijection between nonegative integer matrices and
pairs of semistandard Young tableaux).
Unfortunately, I don't know how to "add it" to the base Matrix class
(like RS is a method from Permutation class, and I don't know if it
should be desirable since it can't be applied to arbitrary matrices)
nor how or where submit it for consideration.
Anyway, here's the code if someone finds it useful
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 algorithm 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)]
Usage:
M = Matrix( [[1,0,2],[0,2,0],[1,1,0]] )
(P,Q)=RSK(Me)
(P,Q)
: ([[1, 1, 2, 2], [2, 3], [3]], [[1, 1, 1, 3], [2, 2], [3]])
P.pp()
1 1 2 2
2 3
3
Q.pp()
1 1 1 3
2 2
3
--
Pedro Sánchez
http://drini.mx
@combinatorica
--
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
