Robinson-Schensted-Knuth correspondence

AUTHORS:

  • Travis Scrimshaw (2012-12-07): Initial version

EXAMPLES:

We can perform RSK and the inverse on a variety of objects:

sage: p = Tableau([[1,2,2],[2]]); q = Tableau([[1,3,3],[2]])
sage: gp = RSK_inverse(p, q); gp
[[1, 2, 3, 3], [2, 1, 2, 2]]
sage: RSK(*gp)
[[[1, 2, 2], [2]], [[1, 3, 3], [2]]]
sage: m = RSK_inverse(p, q, 'matrix'); m
[0 1]
[1 0]
[0 2]
sage: RSK(m)
[[[1, 2, 2], [2]], [[1, 3, 3], [2]]]

TESTS:

Check that it is a correspondence between all types of input and the input is preserved:

sage: t1 = Tableau([[1, 2, 5], [3], [4]])
sage: t2 = Tableau([[1, 2, 3], [4], [5]])
sage: gp = RSK_inverse(t1, t2); gp
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: w = RSK_inverse(t1, t2, 'word'); w
word: 14532
sage: m = RSK_inverse(t1, t2, 'matrix'); m
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: p = RSK_inverse(t1, t2, 'permutation'); p
[1, 4, 5, 3, 2]
sage: t1
[[1, 2, 5], [3], [4]]
sage: t2
[[1, 2, 3], [4], [5]]
sage: RSK(*gp) == [t1, t2]
True
sage: RSK(w) == [t1, t2]
True
sage: RSK(m) == [t1, t2]
True
sage: RSK(p) == [t1, t2]
True
sage: gp
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: w
word: 14532
sage: m
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: p
[1, 4, 5, 3, 2]

REFERENCES:

[Knu1970](1, 2) Donald E. Knuth. Permutations, matrices, and generalized Young tableaux. Pacific J. Math. Volume 34, Number 3 (1970), pp. 709-727. http://projecteuclid.org/euclid.pjm/1102971948
[EG1987](1, 2, 3, 4) Paul Edelman, Curtis Greene. Balanced Tableaux. Advances in Mathematics 63 (1987), pp. 42-99. http://www.sciencedirect.com/science/article/pii/0001870887900636
[BKSTY06](1, 2, 3, 4) A. Buch, A. Kresch, M. Shimozono, H. Tamvakis, and A. Yong. Stable Grothendieck polynomials and \(K\)-theoretic factor sequences. Math. Ann. 340 Issue 2, (2008), pp. 359–382. Arxiv math/0601514v1.
sage.combinat.rsk.RSK(obj1=None, obj2=None, insertion='RSK', check_standard=False, **options)

Perform the Robinson-Schensted-Knuth (RSK) correspondence.

The Robinson-Schensted-Knuth (RSK) correspondence (also known as the RSK algorithm) is most naturally stated as a bijection between generalized permutations (also known as two-line arrays, biwords, ...) and pairs of semi-standard Young tableaux \((P, Q)\) of identical shape. The tableau \(P\) is known as the insertion tableau, and \(Q\) is known as the recording tableau.

The basic operation is known as row insertion \(P \leftarrow k\) (where \(P\) is a given semi-standard Young tableau, and \(k\) is an integer). Row insertion is a recursive algorithm which starts by setting \(k_0 = k\), and in its \(i\)-th step inserts the number \(k_i\) into the \(i\)-th row of \(P\) (we start counting the rows at \(0\)) by replacing the first integer greater than \(k_i\) in the row by \(k_i\) and defines \(k_{i+1}\) as the integer that has been replaced. If no integer greater than \(k_i\) exists in the \(i\)-th row, then \(k_i\) is simply appended to the row and the algorithm terminates at this point.

Now the RSK algorithm, applied to a generalized permutation \(p = ((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell-1}, k_{\ell-1}))\) (encoded as a lexicographically sorted list of pairs) starts by initializing two semi-standard tableaux \(P_0\) and \(Q_0\) as empty tableaux. For each nonnegative integer \(t\) starting at \(0\), take the pair \((j_t, k_t)\) from \(p\) and set \(P_{t+1} = P_t \leftarrow k_t\), and define \(Q_{t+1}\) by adding a new box filled with \(j_t\) to the tableau \(Q_t\) at the same location the row insertion on \(P_t\) ended (that is to say, adding a new box with entry \(j_t\) such that \(P_{t+1}\) and \(Q_{t+1}\) have the same shape). The iterative process stops when \(t\) reaches the size of \(p\), and the pair \((P_t, Q_t)\) at this point is the image of \(p\) under the Robinson-Schensted-Knuth correspondence.

This correspondence has been introduced in [Knu1970], where it has been referred to as “Construction A”.

For more information, see Chapter 7 in [Sta-EC2].

We also note that integer matrices are in bijection with generalized permutations. Furthermore, we can convert any word \(w\) (and, in particular, any permutation) to a generalized permutation by considering the top line to be \((1, 2, \ldots, n)\) where \(n\) is the length of \(w\).

The optional argument insertion allows to specify an alternative insertion procedure to be used instead of the standard Robinson-Schensted-Knuth insertion. If the input is a reduced word of a permutation (i.e., an element of a type-\(A\) Coxeter group), one can set insertion to 'EG', which gives Edelman-Greene insertion, an algorithm defined in [EG1987] Definition 6.20 (where it is referred to as Coxeter-Knuth insertion). The Edelman-Greene insertion is similar to the standard row insertion except that if \(k_i\) and \(k_i + 1\) both exist in row \(i\), we only set \(k_{i+1} = k_i + 1\) and continue.

One can also perform a “Hecke RSK algorithm”, defined using the Hecke insertion studied in [BKSTY06] (but using rows instead of columns). The algorithm proceeds similarly to the classical RSK algorithm. However, it is not clear in what generality it works; thus, following [BKSTY06], we shall assume that our biword \(p\) has top line \((1, 2, \ldots, n)\) (or, at least, has its top line strictly increasing). The Hecke RSK algorithm returns a pair of an increasing tableau and a set-valued standard tableau. If \(p = ((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell-1}, k_{\ell-1}))\), then the algorithm recursively constructs pairs \((P_0, Q_0), (P_1, Q_1), \ldots, (P_\ell, Q_\ell)\) of tableaux. The construction of \(P_{t+1}\) and \(Q_{t+1}\) from \(P_t\), \(Q_t\), \(j_t\) and \(k_t\) proceeds as follows: Set \(i = j_t\), \(x = k_t\), \(P = P_t\) and \(Q = Q_t\). We are going to insert \(x\) into the increasing tableau \(P\) and update the set-valued “recording tableau” \(Q\) accordingly. As in the classical RSK algorithm, we first insert \(x\) into row \(1\) of \(P\), then into row \(2\) of the resulting tableau, and so on, until the construction terminates. The details are different: Suppose we are inserting \(x\) into row \(R\) of \(P\). If (Case 1) there exists an entry \(y\) in row \(R\) such that \(x < y\), then let \(y\) be the minimal such entry. We replace this entry \(y\) with \(x\) if the result is still an increasing tableau; in either subcase, we then continue recursively, inserting \(y\) into the next row of \(P\). If, on the other hand, (Case 2) no such \(y\) exists, then we append \(x\) to the end of \(R\) if the result is an increasing tableau (Subcase 2.1), and otherwise (Subcase 2.2) do nothing. Furthermore, in Subcase 2.1, we add the box that we have just filled with \(x\) in \(P\) to the shape of \(Q\), and fill it with the one-element set \(\{i\}\). In Subcase 2.2, we find the bottommost box of the column containing the rightmost box of row \(R\), and add \(i\) to the entry of \(Q\) in this box (this entry is a set, since \(Q\) is a set-valued). In either subcase, we terminate the recursion, and set \(P_{t+1} = P\) and \(Q_{t+1} = Q\).

Notice that set-valued tableaux are encoded as tableaux whose entries are tuples of positive integers; each such tuple is strictly increasing and encodes a set (namely, the set of its entries).

INPUT:

  • obj1, obj2 – Can be one of the following:
    • A word in an ordered alphabet
    • An integer matrix
    • Two lists of equal length representing a generalized permutation
    • Any object which has a method _rsk_iter() which returns an iterator over the object represented as generalized permutation or a pair of lists.
  • insertion – (Default: 'RSK') The following types of insertion are currently supported:
    • 'RSK' – Robinson-Schensted-Knuth
    • 'EG' – Edelman-Greene (only for reduced words of permutations/elements of a type-\(A\) Coxeter group)
    • 'hecke' – Hecke insertion (only guaranteed for generalized permutations whose top row is strictly increasing)
  • check_standard – (Default: False) Check if either of the resulting tableaux is a standard tableau, and if so, typecast it as such

EXAMPLES:

If we only give one line, we treat the top line as being \((1, 2, \ldots, n)\):

sage: RSK([3,3,2,4,1])
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([3,3,2,4,1]))
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([2,3,3,2,1,3,2,3]))
[[[1, 2, 2, 3, 3], [2, 3], [3]], [[1, 2, 3, 6, 8], [4, 7], [5]]]

With a generalized permutation:

sage: RSK([1, 2, 2, 2], [2, 1, 1, 2])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]
sage: RSK(Word([1,1,3,4,4]), [1,4,2,1,3])
[[[1, 1, 3], [2], [4]], [[1, 1, 4], [3], [4]]]
sage: RSK([1,3,3,4,4], Word([6,2,2,1,7]))
[[[1, 2, 7], [2], [6]], [[1, 3, 4], [3], [4]]]

If we give it a matrix:

sage: RSK(matrix([[0,1],[2,1]]))
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]

We can also give it something looking like a matrix:

sage: RSK([[0,1],[2,1]])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]

There are also variations of the insertion algorithm in RSK. Here we consider Edelman-Greene insertion:

sage: RSK([2,1,2,3,2], insertion='EG')
[[[1, 2, 3], [2, 3]], [[1, 3, 4], [2, 5]]]

We reproduce figure 6.4 in [EG1987]:

sage: RSK([2,3,2,1,2,3], insertion='EG')
[[[1, 2, 3], [2, 3], [3]], [[1, 2, 6], [3, 5], [4]]]

Hecke insertion is also supported. We construct Example 2.1 in Arxiv 0801.1319v2:

sage: w = [5, 4, 1, 3, 4, 2, 5, 1, 2, 1, 4, 2, 4]
sage: RSK(w, insertion='hecke')
[[[1, 2, 4, 5], [2, 4, 5], [3, 5], [4], [5]],
 [[(1,), (4,), (5,), (7,)],
  [(2,), (9,), (11, 13)],
  [(3,), (12,)],
  [(6,)],
  [(8, 10)]]]

There is also RSK_inverse() which performs the inverse of the bijection on a pair of semistandard tableaux. We note that the inverse function takes 2 separate tableaux as inputs, so to compose with RSK(), we need to use the python * on the output:

sage: RSK_inverse(*RSK([1, 2, 2, 2], [2, 1, 1, 2]))
[[1, 2, 2, 2], [2, 1, 1, 2]]
sage: P,Q = RSK([1, 2, 2, 2], [2, 1, 1, 2])
sage: RSK_inverse(P, Q)
[[1, 2, 2, 2], [2, 1, 1, 2]]

TESTS:

Empty objects:

sage: RSK(Permutation([]))
[[], []]
sage: RSK(Word([]))
[[], []]
sage: RSK(matrix([[]]))
[[], []]
sage: RSK([], [])
[[], []]
sage: RSK([[]])
[[], []]
sage: RSK(Word([]), insertion='EG')
[[], []]
sage: RSK(Word([]), insertion='hecke')
[[], []]
sage.combinat.rsk.RSK_inverse(p, q, output='array', insertion='RSK')

Return the generalized permutation corresponding to the pair of tableaux \((p,q)\) under the inverse of the Robinson-Schensted-Knuth algorithm.

For more information on the bijection, see RSK().

INPUT:

  • p, q – Two semi-standard tableaux of the same shape, or (in the case when Hecke insertion is used) an increasing tableau and a set-valued tableau of the same shape (see the note below for the format of the set-valued tableau)

  • output – (Default: 'array') if q is semi-standard:

    • 'array' – as a two-line array (i.e. generalized permutation or biword)
    • 'matrix' – as an integer matrix

    and if q is standard, we can have the output:

    • 'word' – as a word

    and additionally if p is standard, we can also have the output:

    • 'permutation' – as a permutation
  • insertion – (Default: RSK) The insertion algorithm used in the bijection. Currently the following are supported:

    • 'RSK' – Robinson-Schensted-Knuth insertion
    • 'EG' – Edelman-Greene insertion
    • 'hecke' – Hecke insertion

Note

In the case of Hecke insertion, the input variable q should be a set-valued tableau, encoded as a tableau whose entries are strictly increasing tuples of positive integers. Each such tuple encodes the set of its entries.

EXAMPLES:

If both p and q are standard:

sage: t1 = Tableau([[1, 2, 5], [3], [4]])
sage: t2 = Tableau([[1, 2, 3], [4], [5]])
sage: RSK_inverse(t1, t2)
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: RSK_inverse(t1, t2, 'word')
word: 14532
sage: RSK_inverse(t1, t2, 'matrix')
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: RSK_inverse(t1, t2, 'permutation')
[1, 4, 5, 3, 2]
sage: RSK_inverse(t1, t1, 'permutation')
[1, 4, 3, 2, 5]
sage: RSK_inverse(t2, t2, 'permutation')
[1, 2, 5, 4, 3]
sage: RSK_inverse(t2, t1, 'permutation')
[1, 5, 4, 2, 3]

If the first tableau is semistandard:

sage: p = Tableau([[1,2,2],[3]]); q = Tableau([[1,2,4],[3]])
sage: ret = RSK_inverse(p, q); ret
[[1, 2, 3, 4], [1, 3, 2, 2]]
sage: RSK_inverse(p, q, 'word')
word: 1322

In general:

sage: p = Tableau([[1,2,2],[2]]); q = Tableau([[1,3,3],[2]])
sage: RSK_inverse(p, q)
[[1, 2, 3, 3], [2, 1, 2, 2]]
sage: RSK_inverse(p, q, 'matrix')
[0 1]
[1 0]
[0 2]

Using Edelman-Greene insertion:

sage: pq = RSK([2,1,2,3,2], insertion='EG'); pq
[[[1, 2, 3], [2, 3]], [[1, 3, 4], [2, 5]]]
sage: RSK_inverse(*pq, insertion='EG')
[2, 1, 2, 3, 2]

Using Hecke insertion:

sage: w = [5, 4, 1, 3, 4, 2, 5, 1, 2, 1, 4, 2, 4]
sage: pq = RSK(w, insertion='hecke')
sage: RSK_inverse(*pq, insertion='hecke', output='list')
[5, 4, 1, 3, 4, 2, 5, 1, 2, 1, 4, 2, 4]

Note

The constructor of Tableau accepts not only semistandard tableaux, but also arbitrary lists that are fillings of a partition diagram. (And such lists are used, e.g., for the set-valued tableau q that is passed to RSK_inverse(p, q, insertion='hecke').) The user is responsible for ensuring that the tableaux passed to RSK_inverse are of the right types (semistandard, standard, increasing, set-valued as needed).

TESTS:

From empty tableaux:

sage: RSK_inverse(Tableau([]), Tableau([]))
[[], []]

Check that RSK_inverse() is the inverse of RSK() on the different types of inputs/outputs:

sage: f = lambda p: RSK_inverse(*RSK(p), output='permutation')
sage: all(p == f(p) for n in range(7) for p in Permutations(n))
True
sage: all(RSK_inverse(*RSK(w), output='word') == w for n in range(4) for w in Words(5, n))
True
sage: from sage.combinat.integer_matrices import IntegerMatrices
sage: M = IntegerMatrices([1,2,2,1], [3,1,1,1])
sage: all(RSK_inverse(*RSK(m), output='matrix') == m for m in M)
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True

Same for Edelman-Greene (but we are checking only the reduced words that can be obtained using the reduced_word() method from permutations):

sage: g = lambda w: RSK_inverse(*RSK(w, insertion='EG'), insertion='EG', output='permutation')
sage: all(p.reduced_word() == g(p.reduced_word()) for n in range(7) for p in Permutations(n))
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True

Both tableaux must be of the same shape:

sage: RSK_inverse(Tableau([[1,2,3]]), Tableau([[1,2]]))
Traceback (most recent call last):
...
ValueError: p(=[[1, 2, 3]]) and q(=[[1, 2]]) must have the same shape

Check that trac ticket #20430 is fixed:

sage: RSK([1,1,1,1,1,1,1,2,2,2,3], [1,1,1,1,1,1,3,2,2,2,1])
[[[1, 1, 1, 1, 1, 1, 1, 2, 2], [2], [3]],
 [[1, 1, 1, 1, 1, 1, 1, 2, 2], [2], [3]]]
sage: t = SemistandardTableau([[1, 1, 1, 1, 1, 1, 1, 2, 2], [2], [3]])
sage: RSK_inverse(t, t, 'array')
[[1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3],
 [1, 1, 1, 1, 1, 1, 3, 2, 2, 2, 1]]
sage.combinat.rsk.hecke_insertion(obj1, obj2=None)

Return the Hecke insertion of the pair [obj1, obj2].

See also

RSK()

EXAMPLES:

sage: w = [5, 4, 1, 3, 4, 2, 5, 1, 2, 1, 4, 2, 4]
sage: RSK(w, insertion='hecke')
[[[1, 2, 4, 5], [2, 4, 5], [3, 5], [4], [5]],
 [[(1,), (4,), (5,), (7,)],
  [(2,), (9,), (11, 13)],
  [(3,), (12,)],
  [(6,)],
  [(8, 10)]]]
sage.combinat.rsk.hecke_insertion_reverse(p, q, output='array')

Return the reverse Hecke insertion of (p, q).

See also

RSK_inverse()

EXAMPLES:

sage: w = [5, 4, 1, 3, 4, 2, 5, 1, 2, 1, 4, 2, 4]
sage: P,Q = RSK(w, insertion='hecke')
sage: wp = RSK_inverse(P, Q, insertion='hecke', output='list'); wp
[5, 4, 1, 3, 4, 2, 5, 1, 2, 1, 4, 2, 4]
sage: wp == w
True
sage.combinat.rsk.robinson_schensted_knuth(obj1=None, obj2=None, insertion='RSK', check_standard=False, **options)

Perform the Robinson-Schensted-Knuth (RSK) correspondence.

The Robinson-Schensted-Knuth (RSK) correspondence (also known as the RSK algorithm) is most naturally stated as a bijection between generalized permutations (also known as two-line arrays, biwords, ...) and pairs of semi-standard Young tableaux \((P, Q)\) of identical shape. The tableau \(P\) is known as the insertion tableau, and \(Q\) is known as the recording tableau.

The basic operation is known as row insertion \(P \leftarrow k\) (where \(P\) is a given semi-standard Young tableau, and \(k\) is an integer). Row insertion is a recursive algorithm which starts by setting \(k_0 = k\), and in its \(i\)-th step inserts the number \(k_i\) into the \(i\)-th row of \(P\) (we start counting the rows at \(0\)) by replacing the first integer greater than \(k_i\) in the row by \(k_i\) and defines \(k_{i+1}\) as the integer that has been replaced. If no integer greater than \(k_i\) exists in the \(i\)-th row, then \(k_i\) is simply appended to the row and the algorithm terminates at this point.

Now the RSK algorithm, applied to a generalized permutation \(p = ((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell-1}, k_{\ell-1}))\) (encoded as a lexicographically sorted list of pairs) starts by initializing two semi-standard tableaux \(P_0\) and \(Q_0\) as empty tableaux. For each nonnegative integer \(t\) starting at \(0\), take the pair \((j_t, k_t)\) from \(p\) and set \(P_{t+1} = P_t \leftarrow k_t\), and define \(Q_{t+1}\) by adding a new box filled with \(j_t\) to the tableau \(Q_t\) at the same location the row insertion on \(P_t\) ended (that is to say, adding a new box with entry \(j_t\) such that \(P_{t+1}\) and \(Q_{t+1}\) have the same shape). The iterative process stops when \(t\) reaches the size of \(p\), and the pair \((P_t, Q_t)\) at this point is the image of \(p\) under the Robinson-Schensted-Knuth correspondence.

This correspondence has been introduced in [Knu1970], where it has been referred to as “Construction A”.

For more information, see Chapter 7 in [Sta-EC2].

We also note that integer matrices are in bijection with generalized permutations. Furthermore, we can convert any word \(w\) (and, in particular, any permutation) to a generalized permutation by considering the top line to be \((1, 2, \ldots, n)\) where \(n\) is the length of \(w\).

The optional argument insertion allows to specify an alternative insertion procedure to be used instead of the standard Robinson-Schensted-Knuth insertion. If the input is a reduced word of a permutation (i.e., an element of a type-\(A\) Coxeter group), one can set insertion to 'EG', which gives Edelman-Greene insertion, an algorithm defined in [EG1987] Definition 6.20 (where it is referred to as Coxeter-Knuth insertion). The Edelman-Greene insertion is similar to the standard row insertion except that if \(k_i\) and \(k_i + 1\) both exist in row \(i\), we only set \(k_{i+1} = k_i + 1\) and continue.

One can also perform a “Hecke RSK algorithm”, defined using the Hecke insertion studied in [BKSTY06] (but using rows instead of columns). The algorithm proceeds similarly to the classical RSK algorithm. However, it is not clear in what generality it works; thus, following [BKSTY06], we shall assume that our biword \(p\) has top line \((1, 2, \ldots, n)\) (or, at least, has its top line strictly increasing). The Hecke RSK algorithm returns a pair of an increasing tableau and a set-valued standard tableau. If \(p = ((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell-1}, k_{\ell-1}))\), then the algorithm recursively constructs pairs \((P_0, Q_0), (P_1, Q_1), \ldots, (P_\ell, Q_\ell)\) of tableaux. The construction of \(P_{t+1}\) and \(Q_{t+1}\) from \(P_t\), \(Q_t\), \(j_t\) and \(k_t\) proceeds as follows: Set \(i = j_t\), \(x = k_t\), \(P = P_t\) and \(Q = Q_t\). We are going to insert \(x\) into the increasing tableau \(P\) and update the set-valued “recording tableau” \(Q\) accordingly. As in the classical RSK algorithm, we first insert \(x\) into row \(1\) of \(P\), then into row \(2\) of the resulting tableau, and so on, until the construction terminates. The details are different: Suppose we are inserting \(x\) into row \(R\) of \(P\). If (Case 1) there exists an entry \(y\) in row \(R\) such that \(x < y\), then let \(y\) be the minimal such entry. We replace this entry \(y\) with \(x\) if the result is still an increasing tableau; in either subcase, we then continue recursively, inserting \(y\) into the next row of \(P\). If, on the other hand, (Case 2) no such \(y\) exists, then we append \(x\) to the end of \(R\) if the result is an increasing tableau (Subcase 2.1), and otherwise (Subcase 2.2) do nothing. Furthermore, in Subcase 2.1, we add the box that we have just filled with \(x\) in \(P\) to the shape of \(Q\), and fill it with the one-element set \(\{i\}\). In Subcase 2.2, we find the bottommost box of the column containing the rightmost box of row \(R\), and add \(i\) to the entry of \(Q\) in this box (this entry is a set, since \(Q\) is a set-valued). In either subcase, we terminate the recursion, and set \(P_{t+1} = P\) and \(Q_{t+1} = Q\).

Notice that set-valued tableaux are encoded as tableaux whose entries are tuples of positive integers; each such tuple is strictly increasing and encodes a set (namely, the set of its entries).

INPUT:

  • obj1, obj2 – Can be one of the following:
    • A word in an ordered alphabet
    • An integer matrix
    • Two lists of equal length representing a generalized permutation
    • Any object which has a method _rsk_iter() which returns an iterator over the object represented as generalized permutation or a pair of lists.
  • insertion – (Default: 'RSK') The following types of insertion are currently supported:
    • 'RSK' – Robinson-Schensted-Knuth
    • 'EG' – Edelman-Greene (only for reduced words of permutations/elements of a type-\(A\) Coxeter group)
    • 'hecke' – Hecke insertion (only guaranteed for generalized permutations whose top row is strictly increasing)
  • check_standard – (Default: False) Check if either of the resulting tableaux is a standard tableau, and if so, typecast it as such

EXAMPLES:

If we only give one line, we treat the top line as being \((1, 2, \ldots, n)\):

sage: RSK([3,3,2,4,1])
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([3,3,2,4,1]))
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([2,3,3,2,1,3,2,3]))
[[[1, 2, 2, 3, 3], [2, 3], [3]], [[1, 2, 3, 6, 8], [4, 7], [5]]]

With a generalized permutation:

sage: RSK([1, 2, 2, 2], [2, 1, 1, 2])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]
sage: RSK(Word([1,1,3,4,4]), [1,4,2,1,3])
[[[1, 1, 3], [2], [4]], [[1, 1, 4], [3], [4]]]
sage: RSK([1,3,3,4,4], Word([6,2,2,1,7]))
[[[1, 2, 7], [2], [6]], [[1, 3, 4], [3], [4]]]

If we give it a matrix:

sage: RSK(matrix([[0,1],[2,1]]))
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]

We can also give it something looking like a matrix:

sage: RSK([[0,1],[2,1]])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]

There are also variations of the insertion algorithm in RSK. Here we consider Edelman-Greene insertion:

sage: RSK([2,1,2,3,2], insertion='EG')
[[[1, 2, 3], [2, 3]], [[1, 3, 4], [2, 5]]]

We reproduce figure 6.4 in [EG1987]:

sage: RSK([2,3,2,1,2,3], insertion='EG')
[[[1, 2, 3], [2, 3], [3]], [[1, 2, 6], [3, 5], [4]]]

Hecke insertion is also supported. We construct Example 2.1 in Arxiv 0801.1319v2:

sage: w = [5, 4, 1, 3, 4, 2, 5, 1, 2, 1, 4, 2, 4]
sage: RSK(w, insertion='hecke')
[[[1, 2, 4, 5], [2, 4, 5], [3, 5], [4], [5]],
 [[(1,), (4,), (5,), (7,)],
  [(2,), (9,), (11, 13)],
  [(3,), (12,)],
  [(6,)],
  [(8, 10)]]]

There is also RSK_inverse() which performs the inverse of the bijection on a pair of semistandard tableaux. We note that the inverse function takes 2 separate tableaux as inputs, so to compose with RSK(), we need to use the python * on the output:

sage: RSK_inverse(*RSK([1, 2, 2, 2], [2, 1, 1, 2]))
[[1, 2, 2, 2], [2, 1, 1, 2]]
sage: P,Q = RSK([1, 2, 2, 2], [2, 1, 1, 2])
sage: RSK_inverse(P, Q)
[[1, 2, 2, 2], [2, 1, 1, 2]]

TESTS:

Empty objects:

sage: RSK(Permutation([]))
[[], []]
sage: RSK(Word([]))
[[], []]
sage: RSK(matrix([[]]))
[[], []]
sage: RSK([], [])
[[], []]
sage: RSK([[]])
[[], []]
sage: RSK(Word([]), insertion='EG')
[[], []]
sage: RSK(Word([]), insertion='hecke')
[[], []]
sage.combinat.rsk.robinson_schensted_knuth_inverse(p, q, output='array', insertion='RSK')

Return the generalized permutation corresponding to the pair of tableaux \((p,q)\) under the inverse of the Robinson-Schensted-Knuth algorithm.

For more information on the bijection, see RSK().

INPUT:

  • p, q – Two semi-standard tableaux of the same shape, or (in the case when Hecke insertion is used) an increasing tableau and a set-valued tableau of the same shape (see the note below for the format of the set-valued tableau)

  • output – (Default: 'array') if q is semi-standard:

    • 'array' – as a two-line array (i.e. generalized permutation or biword)
    • 'matrix' – as an integer matrix

    and if q is standard, we can have the output:

    • 'word' – as a word

    and additionally if p is standard, we can also have the output:

    • 'permutation' – as a permutation
  • insertion – (Default: RSK) The insertion algorithm used in the bijection. Currently the following are supported:

    • 'RSK' – Robinson-Schensted-Knuth insertion
    • 'EG' – Edelman-Greene insertion
    • 'hecke' – Hecke insertion

Note

In the case of Hecke insertion, the input variable q should be a set-valued tableau, encoded as a tableau whose entries are strictly increasing tuples of positive integers. Each such tuple encodes the set of its entries.

EXAMPLES:

If both p and q are standard:

sage: t1 = Tableau([[1, 2, 5], [3], [4]])
sage: t2 = Tableau([[1, 2, 3], [4], [5]])
sage: RSK_inverse(t1, t2)
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: RSK_inverse(t1, t2, 'word')
word: 14532
sage: RSK_inverse(t1, t2, 'matrix')
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: RSK_inverse(t1, t2, 'permutation')
[1, 4, 5, 3, 2]
sage: RSK_inverse(t1, t1, 'permutation')
[1, 4, 3, 2, 5]
sage: RSK_inverse(t2, t2, 'permutation')
[1, 2, 5, 4, 3]
sage: RSK_inverse(t2, t1, 'permutation')
[1, 5, 4, 2, 3]

If the first tableau is semistandard:

sage: p = Tableau([[1,2,2],[3]]); q = Tableau([[1,2,4],[3]])
sage: ret = RSK_inverse(p, q); ret
[[1, 2, 3, 4], [1, 3, 2, 2]]
sage: RSK_inverse(p, q, 'word')
word: 1322

In general:

sage: p = Tableau([[1,2,2],[2]]); q = Tableau([[1,3,3],[2]])
sage: RSK_inverse(p, q)
[[1, 2, 3, 3], [2, 1, 2, 2]]
sage: RSK_inverse(p, q, 'matrix')
[0 1]
[1 0]
[0 2]

Using Edelman-Greene insertion:

sage: pq = RSK([2,1,2,3,2], insertion='EG'); pq
[[[1, 2, 3], [2, 3]], [[1, 3, 4], [2, 5]]]
sage: RSK_inverse(*pq, insertion='EG')
[2, 1, 2, 3, 2]

Using Hecke insertion:

sage: w = [5, 4, 1, 3, 4, 2, 5, 1, 2, 1, 4, 2, 4]
sage: pq = RSK(w, insertion='hecke')
sage: RSK_inverse(*pq, insertion='hecke', output='list')
[5, 4, 1, 3, 4, 2, 5, 1, 2, 1, 4, 2, 4]

Note

The constructor of Tableau accepts not only semistandard tableaux, but also arbitrary lists that are fillings of a partition diagram. (And such lists are used, e.g., for the set-valued tableau q that is passed to RSK_inverse(p, q, insertion='hecke').) The user is responsible for ensuring that the tableaux passed to RSK_inverse are of the right types (semistandard, standard, increasing, set-valued as needed).

TESTS:

From empty tableaux:

sage: RSK_inverse(Tableau([]), Tableau([]))
[[], []]

Check that RSK_inverse() is the inverse of RSK() on the different types of inputs/outputs:

sage: f = lambda p: RSK_inverse(*RSK(p), output='permutation')
sage: all(p == f(p) for n in range(7) for p in Permutations(n))
True
sage: all(RSK_inverse(*RSK(w), output='word') == w for n in range(4) for w in Words(5, n))
True
sage: from sage.combinat.integer_matrices import IntegerMatrices
sage: M = IntegerMatrices([1,2,2,1], [3,1,1,1])
sage: all(RSK_inverse(*RSK(m), output='matrix') == m for m in M)
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True

Same for Edelman-Greene (but we are checking only the reduced words that can be obtained using the reduced_word() method from permutations):

sage: g = lambda w: RSK_inverse(*RSK(w, insertion='EG'), insertion='EG', output='permutation')
sage: all(p.reduced_word() == g(p.reduced_word()) for n in range(7) for p in Permutations(n))
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True

Both tableaux must be of the same shape:

sage: RSK_inverse(Tableau([[1,2,3]]), Tableau([[1,2]]))
Traceback (most recent call last):
...
ValueError: p(=[[1, 2, 3]]) and q(=[[1, 2]]) must have the same shape

Check that trac ticket #20430 is fixed:

sage: RSK([1,1,1,1,1,1,1,2,2,2,3], [1,1,1,1,1,1,3,2,2,2,1])
[[[1, 1, 1, 1, 1, 1, 1, 2, 2], [2], [3]],
 [[1, 1, 1, 1, 1, 1, 1, 2, 2], [2], [3]]]
sage: t = SemistandardTableau([[1, 1, 1, 1, 1, 1, 1, 2, 2], [2], [3]])
sage: RSK_inverse(t, t, 'array')
[[1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3],
 [1, 1, 1, 1, 1, 1, 3, 2, 2, 2, 1]]
sage.combinat.rsk.to_matrix(t, b)

Return the integer matrix corresponding to a two-line array.

INPUT:

  • t – The top line of the array
  • b – The bottom line of the array

OUTPUT:

An \(m \times n\)-matrix (where \(m\) and \(n\) are the maximum entries in \(t\) and \(b\) respectively) whose \((i, j)\)-th entry, for any \(i\) and \(j\), is the number of all positions \(k\) satisfying \(t_k = i\) and \(b_k = j\).

EXAMPLES:

sage: from sage.combinat.rsk import to_matrix
sage: to_matrix([1, 1, 3, 3, 4], [2, 3, 1, 1, 3])
[0 1 1]
[0 0 0]
[2 0 0]
[0 0 1]