Implementation of the Robinson-Schensted Correspondence

Has the Robinson-Schensted correspondence, as explained by Wikipedia or Richard Stanley, been implemented in any of the standard programming languages. I'm using Python, but I'm open to Java, C++, Mathematica, Matlab. On paper, the bumping is not so bad - I think 1364752 gives you a v-shaped tableau - but coding the algorithm may require linked lists.

The regular representation of a finite group can be decomposed into a direct sum of all the irreducible representations of G. The basis of the right-regular representation is the elements $g \in G$ and the group action is $\rho_g(h) = hg$. Then every irreducible representation appears in the sum with multiplicity equal to its dimension $$|G| = \sum_{\pi \in \text{Irr(G)}} (\dim \pi )^2$$ When G = S(n), the permutation group on n elements, the irreducible representations are indexed by Young-diagrams with n boxes and |G| = n!

The Robinson-Schensted correspondence takes this literally and bijectively takes in a permutation and spits out two pairs of (standard?) Young tableaux filled with numbers 1 thru n of the same shape.

-
Both links seem to be broken. – Daniel Litt Jul 7 '10 at 16:11
Fixed. Do you think I should put in an explanation of RSK? – john mangual Jul 7 '10 at 16:24
In case you are interested in generality: I have an implementation of Fomin's growth diagrams in FriCAS. It should be straightforward to port to any other language. – Martin Rubey Jul 7 '10 at 17:31

It doesn't require linked lists, just arrays that can grow.

There's a Java applet online that implements it.

I'm sure there are other implementations online, but since I couldn't find any, as a start, here's a simple Python implementation. [Though it feels odd giving a programming answer here, and I'm sure several people here can write it much better!]

from bisect import bisect
def RSK(p):
'''Given a permutation p, spit out a pair of Young tableaux'''
P = []; Q = []
def insert(m, n=0):
'''Insert m into P, then place n in Q at the same place'''
for r in range(len(P)):
if m > P[r][-1]:
P[r].append(m); Q[r].append(n)
return
c = bisect(P[r], m)
P[r][c],m = m,P[r][c]
P.append([m])
Q.append([n])

for i in range(len(p)):
insert(int(p[i]), i+1)
return (P,Q)

print RSK('1364752')


Edit: Used binary search to improve from O(n3) to O(n2log n), which should matter only for very large permutations.

-
very nice. this saves me a lot of time. – john mangual Jul 7 '10 at 16:59
Great, glad to help. I've edited the code, but the "insert" function inside can still be used separately if you want to run it on two sequences instead of a single permutation. – shreevatsa Jul 7 '10 at 17:14

This is certainly implemented in Sage,

http://www.sagemath.org/doc/reference/sage/combinat/permutation.html

and you can run Sage at http://sagenb.org/

I am sure there are other possibilities.

-
This is good especially since I work with Python. Is it possible to call the libraries directly rather than use the notebook (should I need to)? – john mangual Jul 7 '10 at 16:46
Just because you can do something doesn't mean it's a good idea (as I have to explain to my children). Since sage is open source you might be able to but I doubt it's a good idea. You can of course install sage (on windows you also need to simulate linux). For your question as stated this doesn't sound worthwhile but if you want more it could be. – Bruce Westbury Jul 7 '10 at 17:01

The Combinatorica package of Mathematica does it with the function PermutationToTableaux

p={1,3,6,4,7,5,2};
t=PermutationToTableaux[p];
t[[1]]//TableForm (* the P table *)

1 2 4 5
3 7
6

t[[2]]//TableForm (* the Q table *)
1 2 3 5
4 6
7

-

With R:

bump <- function(P, Q, e, i){
if(length(P)==0) return(list(P=list(e), Q=list(i)))
if(e > P[[1]][length(P[[1]])]){
P[[1]] <- c(P[[1]], e)
Q[[1]] <- c(Q[[1]], i)
return(list(P=P, Q=Q))
}else{
j <- which.min(P[[1]]<e)
w <- P[[1]][j]
P[[1]][j] <- e
b <- bump(P[-1], Q[-1], w, i)
return(list(P=c(P[1], b$P), Q=c(Q[1], b$Q)))
}
}
RKS <- function(sigma){
out <- bump(list(), list(), sigma[1], 1)
for(i in 2:length(sigma)){
out <- bump(out$P, out$Q, sigma[i], i)
}
return(out)
}


It seems to work well:

> sigma <- c(1, 3, 6, 4, 7, 5, 2)
> RKS(sigma)
$P$P[[1]]
[1] 1 2 4 5

$P[[2]] [1] 3 7$P[[3]]
[1] 6

$Q$Q[[1]]
[1] 1 2 3 5

$Q[[2]] [1] 4 6$Q[[3]]
[1] 7

-