MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 9 down vote accepted

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)
            c = bisect(P[r], m)
            P[r][c],m = m,P[r][c]

    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.

share|cite|improve this answer
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,

and you can run Sage at

I am sure there are other possibilities.

share|cite|improve this answer
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

t[[1]]//TableForm (* the P table *)

1 2 4 5
3 7

t[[2]]//TableForm (* the Q table *)
1 2 3 5 
4 6
share|cite|improve this answer

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))
    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)

It seems to work well:

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

[1] 3 7

[1] 6

[1] 1 2 3 5

[1] 4 6

[1] 7
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.