Viennot's construction, named for Xavier Gérard Viennot, is a method of finding the ordered pair \((P, Q)\) of standard tableaux that correspond to a permutation, as predicted by the Robinson-Schensted correspondence.
Given a permutation \(\sigma\) on \(n\) letters, the process begins by plotting the points \( (i, \sigma(i))\) for \(1 \leq i \leq n\). Next, imagine a light shining from the origin towards the first quadrant of a plane, resulting in each point casting a shadow towards the north east. The boundaries of these shadows reveal the first row of the tableaux. Before removing the first set of shadows, draw new points at the new vertices of the shadow lines, and repeat the process to find the successive rows of the tableaux. The process is complete when no shadow lines have any remaining vertices.
Using the Applet
Choose a size for your permutation, then enter the permutation (in two line notation). The applet will check that your map defines a bijective map on the set. Once a valid permutation is enter, click the 'Continue building tableaux' button until all rows of the tableaux are discovered. The tableaux with a white background is the tableau \(P\), and the tableau \(Q\) has a dark background. Hover or touch the boxes in the tableaux to highlight the corresponding shadow line.
While there is no upper bound on the size of your permutation in the code, the size of your screen may make larger permutations difficult to work with.
About this Applet