MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 bisect

It's not so hard to implement, and

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 although I'm sure several people here can write it much betterbetter!]

from bisect import bisect
def RSK(p):
'''Given a permutation p, here's spit out a Python implementation that takes O(n2) per element inserted. Binary search can improve it to O(n log n).

'''The bumping algorithm for 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)):
l = len(P[r])
if m > P[r][l-1]P[r][-1]:
P[r].append(m)
P[r].append(m); Q[r].append(n)
return
for c in range(l):
if P[r][c] > = bisect(P[r], m:
)
P[r][c],m = m,P[r][c]
break
P.append([m])
Q.append([n])

s = '1364752'
for i in range(len(s))range(len(p)):
insert(int(s[i])insert(int(p[i]), i+1)
print P
return (P,Q)

print Q
RSK('1364752')

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


 
 
 
1

It's not so hard to implement, and 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, and although several people here can write it much better, here's a Python implementation that takes O(n2) per element inserted. Binary search can improve it to O(n log n).

'''The bumping algorithm for 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)):
l = len(P[r])
if m > P[r][l-1]:
P[r].append(m)
Q[r].append(n)
return
for c in range(l):
if P[r][c] > m:
P[r][c],m = m,P[r][c]
break
P.append([m])
Q.append([n])

s = '1364752'
for i in range(len(s)):
insert(int(s[i]), i+1)

print P
print Q