Robinson Schensted correspondence

Question

[The explanations of the algorithm come from here. I recommend reading it for a beautiful description of the algorithm.]

This challenge is to implement the Robinson Schensted correspondence.

Input

A permutation \$\pi\$ of the integers \$\{1, \dots, n\}\$.

Output

A pair of Young Tableaux corresponding to the Robinson Schensted correspondence of \$\pi\$.

Explanation

A Young Tableau of size \$n\$ is a two-dimensional arrangement of the numbers from \$1\$ to \$n\$, in which each number appears exactly once. They are arranged in left-justified rows, one below the other, and no row has more entries than the one above it. Also, the entries in each row are in increasing order as you read them from left to right, and the entries in each column are in increasing order as you read them from top to bottom. citation

The Robinson-Schensted algorithm takes a permutation of the numbers \$1\$ to \$n\$ and produces two Young Tableaux from it. We call these two tableaux \$P\$ and \$Q\$.

I will describe how to make \$P\$ first.

Given a permutation \$a_1, \dots, a_n\$, we process the numbers in the permutation from left to right. We try to insert them one after another into a growing Young tableau, making new rows where we can't do it while satisfying the conditions that the entries in each row are in increasing order as you read them from left to right.

We start with \$a_1\$ and place it in the top left. We then try to place \$a_2\$ to its right. If \$a_2 < a_1\$ then we make a new row, place \$a_1\$ in the new row on the left and place \$a_2\$ in the top left. If \$a_2 > a_1\$ then we simply append it to the first row. Now consider \$a_3\$. If it is larger than all the numbers in the first row we simply append it to the first row. If not, we find the first number in the first row that is larger than it and replace that number with \$a_3\$. We now take the number that we replaced, and we insert it into the second row, in the same way as before. This may cause a number to be "bumped" out of the second row and inserted into the third row. We keep going in the same way all through the permutation, always inserting the next number from our permutation starting at the first row of the tableau.

\$Q\$ has the same shape as \$P\$, but we just number the boxes by the step at which that box appeared in \$P\$.

Examples

pi = [2 1 3]
P = [[1, 3], [2]]
Q = [[1, 3], [2]]
pi = [1 3 2 4]
P = [[1, 2, 4], [3]]
Q = [[1, 2, 4], [3]]
pi = [5 3 4 1 2]
P = [[1, 2], [3, 4], [5]]
Q = [[1, 3], [2, 5], [4]]
pi = [1 5 6 4 2 3]
P = [[1, 2, 3], [4, 6], [5]]
Q = [[1, 2, 3], [4, 6], [5]]
pi = [4 2 6 5 7 3 1]
P = [[1, 3, 7], [2, 5], [4], [6]]
Q = [[1, 3, 5], [2, 4], [6], [7]]

Answer 1

Charcoal, 66 bytes

≔Ｅθ⟦⟧ηＦθ«≔⁰ζＷΦ§ηζ›λ髧≔§ηζ⌕§ηζ⌊κι≔⌊κι≦⊕ζ»⊞§ηζι⊞υζ»Ｅ⟦η⊕Ｅθ⌕Ａυκ⟧⭆¹Φιν

Try it online! Link is to verbose version of code. Explanation:

≔Ｅθ⟦⟧η

Create P with an array for each entry, just in case.

Ｆθ«

Loop over the input list.

≔⁰ζ

Start at the first array of P.

ＷΦ§ηζ›λι«

Repeat while the current array of P has elements greater than the current value.

§≔§ηζ⌕§ηζ⌊κι

Replace the next greater element with the current value.

≔⌊κι

Replace the current value with the next greater element.

≦⊕ζ

Move to the next array of P.

»⊞§ηζι

Append the current value to the current array of P.

⊞υζ

Keep a record of the insertion indices.

»Ｅ⟦η⊕Ｅθ⌕Ａυκ⟧⭆¹Φιν

Build Q from the list of insertion indices, then trim trailing empty elements from both P and Q and pretty-print them at a cost of 1 byte (the default output format isn't terribly readable).

Answer 2

JavaScript (ES12), 124 bytes

Returns [P, Q].

a=>a.map(g=v=>(p=P[y]||=[]).some((V,k)=>V>v?p[n=V,k]=v:0)?g(n,y++):y=(Q[y]||=[]).push(++j)^p.push(v),y=j=0,Q=[],P=[])&&[P,Q]

Attempt This Online!

Commented

a =>                // a[] = input array
a.map(g =           // using a recursive callback function g,
  v =>              // for each value v in a[]:
  ( p =             //   p[] is the entry at position
      P[y] ||= []   //   y in P[] (initialized to [] if undefined)
  )                 //
  .some((V, k) =>   //   for each value V at index k in p[]:
    V > v ?         //     if V is greater than v:
      p[n = V, k]   //       save V in n
      = v           //       set p[k] to v and trigger the some()
    :               //     else:
      0             //       keep searching
  )                 //   end of some()
  ?                 //   if found:
    g(n, y++)       //     do a recursive call with v = n
                    //     and y incremented
  :                 //   else:
    y =             //     save in y:
      (Q[y] ||= []) //       initialize Q[y] to [] if undefined
      .push(++j) ^  //       increment j and push it in Q[y]
      p.push(v),    //       push v in p[]
                    //     p[] and Q[y] have the same length L,
                    //     so this resets y to (L xor L) == 0
  y = j = 0,        //   start with y = 0 and j = 0
  Q = [],           //   initialize Q[]
  P = []            //   initialize P[]
) && [ P, Q ]       // end of map(); return [ P, Q ]

Answer 3

R, 115 bytes

\(x){P=Q=!x%o%x;for(i in x){r=1;while(i<-P[r,w<-which.min(P[r,]%in%1:i)]-!(P[r,w]=i))r=r+1;Q[r,w]=F=F+1};list(P,Q)}

Attempt This Online!

For an input vector of length \$n\$, this returns a pair of \$n \times n\$ matrices initialized with zeros and the actual content of tableaux filled in. I hope, that's an acceptable output format.

Explanation

\(x) {
  P=Q=!x%o%x                    # Initialize the matrices
  for (i in x) {                # Loop through the elements
    r=1                         # Start at row 1. We can't abuse built-in T here
                                # as it has to be reset on each iteration
    while ({
      w=which.min(P[r,]%in%1:i) # Find the first element in the current row that is >i or 0
      i=P[r,w]-!(P[r,w]=i)      # Swap the found element with i
    i})                         # While we are not on 0 (empty space)
      r=r+1                     # Go to the next row
    Q[r,w]=F=F+1                # When finished, increase the turn number and store it in Q
  }
  list(P,Q)                     #... and return
}

Answer 4

Python3, 559 bytes

E=enumerate
from itertools import*
Z=zip_longest
W=lambda x:[[*filter(None,i)]for i in x]
V=lambda X:all(all(x[i]<x[i+1]for i in range(len(x)-1))for x in X)
def U(p,a):p[0]+=[a]
def G(P,a,I):P[I-1]=[*P[I-1][:len(P[I])],P[I][-1],*P[I-1][len(P[I]):]];P[I]=[a,*P[I][:-1]]
def f(l):
 p,q=[[l.pop(0)]],[[1]]
 for i,a in E(l,2):
  F=1
  for I,v in E(p[0]):
   if v>a:
    F=0;P=W(Z(*p));Q=W(Z(*q));P[I]=[a,*P[I]];Q[I]=[i,*Q[I]]
    if V(W(Z(*P)))==0:P[I]=P[I][1:];Q[I]=Q[I][:-1];G(P,a,I);G(Q,i,I)
    p=W(Z(*P));q=W(Z(*Q))
    break
  if F:U(p,a);U(q,i)
 return p,q

Try it online!

Answer 5

J, 60 bytes

g=.<`(/:~(-.;$:@])&;2<@-./\_"+]F:.(]`I.`[}~)])@.(1<#)
,:&g/:

Attempt This Online! (Note: code won't actually run because ATO's J isn't new enough. See below for how to run locally.)

The idea

Consider input 4 2 6 5 7 3 1:

• Fold forward through the input, collecting results. Seed the fold with a list of infinity repeated n times, where n is the input length. The fold logic is...

• At each step, find the "insert before" point for the next element (where you'd need to insert it to maintain ascending order), but instead of inserting, overwrite the list at that position. For our example input, the result would be:

  4 _ _ _ _ _ _
  2 _ _ _ _ _ _
  2 6 _ _ _ _ _
  2 5 _ _ _ _ _
  2 5 7 _ _ _ _
  2 3 7 _ _ _ _
  1 3 7 _ _ _ _
  

• Notice the final row 1 3 7 already contains the first row of the P Young tableaux. We also need the 4 evicted elements, in order of eviction, to call the function recursively and so build the entire tableaux.

• To find them, take the set difference of every pair of rows. This difference will be empty when the fold appends an element, and it will be the evicted element when the fold overwrites:

  ┌─┬┬─┬┬─┬─┐
  │4││6││5│2│
  └─┴┴─┴┴─┴─┘
  

• Next, append to 1 3 7 the result of running the above procedure recursively on 4 6 5 2. This gives us the P tableaux.

• Finally, to get the Q tableaux, we do everything again on the "grade up" of the input, rather than the input itself.

Alternate way to find evicted elements

It's worth pointing out this alternate approach to finding the evicted elements from the cumulative fold result, since it may help submissions in other languages.

• Take the fold result above, remove the infinity placeholders, and flatten it:

  4 2 2 6 2 5 2 5 7 2 3 7 1 3 7
  

• Remove the final row elements 1 3 7:

  4 2 2 6 2 5 2 5 2
  

• Take the uniq, but start at the right side instead of the left:

  2 5 6 4
  

  This is exactly the reverse of what we need. So uniq "under" reverse ~.&.|. produces the evicted elements in the correct order:

  4 6 5 2
  

The full J code for this approach is:

g=.<`([:({:,~.&.|.&;$:@-.;@{:)_"+<F:.(]`I.`[}~)])@.(1<#)
,:&g/:

Local tests

These tests require J 9.4.2.

The code expects 0-indexed input and produces 0-indexed output. However, to keep the test readable, we do pre- and post-processing below so that the actual input/output is 1-indexed.

g=.<`(/:~(-.;$:@])&;2<@-./\_"+]F:.(]`I.`[}~)])@.(1<#)
f=.,:&g/:

>:L:0 f <: 5 3 4 1 2
>:L:0 f <: 1 5 6 4 2 3
>:L:0 f <: 4 2 6 5 7 3 1
>:L:0 f <: 1 2 3 4
>:L:0 f <: 4 3 2 1

Running the above produces:

  >:L:0 f <: 5 3 4 1 2
┌───┬───┬─┐
│1 2│3 4│5│
├───┼───┼─┤
│1 3│2 5│4│
└───┴───┴─┘
  >:L:0 f <: 1 5 6 4 2 3
┌─────┬───┬─┐
│1 2 3│4 6│5│
├─────┼───┼─┤
│1 2 3│4 6│5│
└─────┴───┴─┘
  >:L:0 f <: 4 2 6 5 7 3 1
┌─────┬───┬─┬─┐
│1 3 7│2 5│4│6│
├─────┼───┼─┼─┤
│1 3 5│2 4│6│7│
└─────┴───┴─┴─┘
  >:L:0 f <: 1 2 3 4
┌───────┬─┐
│1 2 3 4│_│
├───────┼─┤
│1 2 3 4│_│
└───────┴─┘
  >:L:0 f <: 4 3 2 1
┌─┬─┬─┬─┐
│1│2│3│4│
├─┼─┼─┼─┤
│1│2│3│4│
└─┴─┴─┴─┘

Note the 2nd to last test case contains an extraneous blank, but this is allowed.

Answer 6

Haskell, 177 bytes

import Data.List
h([],_,n)x=([[x]],[[n]],n+1)
h(p:w,q:z,n)x|(t,y:d)<-span(x>)p,(w,z,m)<-h(w,z,n)y=((t++x:d):w,q:z,m)
h(p:w,q:z,n)x=((p++[x]):w,(q++[n]):z,n+1)
f=foldl h([],[],1)

Attempt This Online!