This page animates the insertion procedure, or bumping procedure, of the Domino Robinson-Schensted algorithm.
To start, you need an input signed permutation. This can be obtained in two ways. First, you can have the page generate a random signed permutation. To do that, enter the size of the desired permutation in the first textbox.
Instead, you can enter a signed permutation, for example, 2 -5 3 6 -4 1, in the second textbox. To do that, list the numbers of the permutation, separated by spaces.
The easiest way to run the animation is to press Enter while in the textbox in which you have placed your input. The first time you press Enter, the page will start the animation. After that, it will do the next step. You can press Enter while in the middle of an animation step, to go on to the next step. If you press Enter after the animation is completed, this will start a new animation.
If you want go to a different input while still in the middle of a previous input, you can enter your information into one of the textboxes, and then press the Start Animation button to the right of that textbox. After that, click the adjacent "Next Step" button, or return focus to the textbox. Then, you can continue the animation by pressing Enter, as above.
You can alter the speed of the animation using the dropdown menu.
The Domino Robinson-Schensted algorithm is a relatively straightforward generalization of the Robinson-Schensted algorithm to the hyperoctrahedral group, that is, the group of signed permutations. The input to the Domino Robinson-Schensted algorithm is a "signed permutation", for example, 2 -5 3 6 -4 1. That is, the numbers 1 through n are permuted, and, in addition, each number has a sign (or orientation) associated with it. The output of the Domino Robinson-Schensted algorithm is a pair of domino tableaux with the same shape. That is, instead of a tableau being made of squares, it is made of 2 x 1 shapes (dominos), which can be horizontal or vertical in the tableau. However, unlike the dominos in a game, each domino has only one number in it.
As in the original Robinson-Schensted algorithm, the left tableau is the insertion, or bumping, tableau. The right tableau is the recording tableau. In this algorithm, insertion is either as a horizontal domino in the first row, if the number in the signed permutation is positive, or as a vertical domino in the first column, if the number in the signed permutation is positive. Bumping is also more complicated. A horizontal domino which is bumped entirely moves to the next row below. A vertical domino which is bumped entirely moves to the next column to the right. A domino which is bumped in one square rotates down and to the right on its unbumped square.