AUTHORS:
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 |
Perform the Robinson-Schensted-Knuth (RSK) correspondence.
The Robinson-Schensted-Knuth (RSK) correspondence 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\) 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 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 \(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. In addition, we can also convert any word \(w\) (and 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., a type \(A\) Coxeter element), 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.
INPUT:
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, and currently only Edelman-Greene insertion is supported:
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]]]
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 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')
[[], []]
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 bijeciton, see RSK().
INPUT:
p, q – Two semi-standard tableaux of the same shape
output – (Default: 'array') if q is semi-standard:
and if q is standard, we can have the output:
and additionally if p is standard, we can also have the output:
insertion – (Default: RSK) The insertion algorithm used in the bijection. Currently only 'RSK' and 'EG' (Edelman-Greene) are supported.
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 the Edelman-Greene insertion:
sage: pq = RSK([2,1,2,3,2], insertion='RSK'); pq
[[[1, 2, 2], [2, 3]], [[1, 3, 4], [2, 5]]]
sage: RSK_inverse(*pq, insertion='EG')
[2, 1, 2, 3, 2]
Note
Currently the constructor of Tableau accept as input lists that are not even tableaux but only filling of a partition diagram. This feature should not be used with RSK_inverse.
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
Perform the Robinson-Schensted-Knuth (RSK) correspondence.
The Robinson-Schensted-Knuth (RSK) correspondence 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\) 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 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 \(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. In addition, we can also convert any word \(w\) (and 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., a type \(A\) Coxeter element), 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.
INPUT:
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, and currently only Edelman-Greene insertion is supported:
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]]]
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 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')
[[], []]
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 bijeciton, see RSK().
INPUT:
p, q – Two semi-standard tableaux of the same shape
output – (Default: 'array') if q is semi-standard:
and if q is standard, we can have the output:
and additionally if p is standard, we can also have the output:
insertion – (Default: RSK) The insertion algorithm used in the bijection. Currently only 'RSK' and 'EG' (Edelman-Greene) are supported.
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 the Edelman-Greene insertion:
sage: pq = RSK([2,1,2,3,2], insertion='RSK'); pq
[[[1, 2, 2], [2, 3]], [[1, 3, 4], [2, 5]]]
sage: RSK_inverse(*pq, insertion='EG')
[2, 1, 2, 3, 2]
Note
Currently the constructor of Tableau accept as input lists that are not even tableaux but only filling of a partition diagram. This feature should not be used with RSK_inverse.
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
Return the integer matrix corresponding to a two-line array.
INPUT:
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]