Question

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.

Answer 1

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(n³) to O(n²log n), which should matter only for very large permutations.

Answer 2

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.

Answer 3

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