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 |
-
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 is most naturally stated as a bijection between generalized permutations (also known as two-line arrays, biwords, ...) and pairs of semi-standard Young tableaux
of identical shape. The tableau
is known as the insertion tableau and
is known as the recording tableau.
The basic operation is known as row insertion
(where
is a given semi-standard Young tableau, and
is an integer). Row insertion is a recursive algorithm which starts by setting
, and in its
-th step inserts the number
into the
-th row of
by replacing the first integer greater than
in the row by
and defines
as the integer that has been replaced. If no integer greater than
exists in the
-th row, then
is simply appended to the row and the algorithm terminates at this point.
Now the RSK algorithm starts by initializing two semi-standard tableaux
and
as empty tableaux. For each nonnegative integer
starting at
, take the pair
from
and set
, and define
by adding a new box filled with
to the tableau
at the same location the row insertion on
ended (that is to say, adding
such that
and
have the same shape). The iterative process stops when
reaches the size of
, and the pair
at this point is the image of
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
(and any permutation) to a generalized permutation by considering the top line to be
where
is the length of
.
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 typeCoxeter 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 ifand
both exist in row
, we only set
and continue.
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/typeCoxeter elements)
check_standard
– (Default:False
) Check if either of the resulting tableaux should be standard tableau.
EXAMPLES:
If we only give one line, we treat the top line as being
:
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 withRSK()
, 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.combinat.rsk.
RSK_inverse
(p, q, output='array', insertion='RSK')¶ Return the generalized permutation corresponding to the pair of tableaux
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 shapeoutput
– (Default:'array'
) ifq
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 only'RSK'
and'EG'
(Edelman-Greene) are supported.
EXAMPLES:
If both
p
andq
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 withRSK_inverse
.TESTS:
From empty tableaux:
sage: RSK_inverse(Tableau([]), Tableau([])) [[], []]
Check that
RSK_inverse()
is the inverse ofRSK()
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
-
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 is most naturally stated as a bijection between generalized permutations (also known as two-line arrays, biwords, ...) and pairs of semi-standard Young tableaux
of identical shape. The tableau
is known as the insertion tableau and
is known as the recording tableau.
The basic operation is known as row insertion
(where
is a given semi-standard Young tableau, and
is an integer). Row insertion is a recursive algorithm which starts by setting
, and in its
-th step inserts the number
into the
-th row of
by replacing the first integer greater than
in the row by
and defines
as the integer that has been replaced. If no integer greater than
exists in the
-th row, then
is simply appended to the row and the algorithm terminates at this point.
Now the RSK algorithm starts by initializing two semi-standard tableaux
and
as empty tableaux. For each nonnegative integer
starting at
, take the pair
from
and set
, and define
by adding a new box filled with
to the tableau
at the same location the row insertion on
ended (that is to say, adding
such that
and
have the same shape). The iterative process stops when
reaches the size of
, and the pair
at this point is the image of
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
(and any permutation) to a generalized permutation by considering the top line to be
where
is the length of
.
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 typeCoxeter 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 ifand
both exist in row
, we only set
and continue.
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/typeCoxeter elements)
check_standard
– (Default:False
) Check if either of the resulting tableaux should be standard tableau.
EXAMPLES:
If we only give one line, we treat the top line as being
:
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 withRSK()
, 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.combinat.rsk.
robinson_schensted_knuth_inverse
(p, q, output='array', insertion='RSK')¶ Return the generalized permutation corresponding to the pair of tableaux
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 shapeoutput
– (Default:'array'
) ifq
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 only'RSK'
and'EG'
(Edelman-Greene) are supported.
EXAMPLES:
If both
p
andq
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 withRSK_inverse
.TESTS:
From empty tableaux:
sage: RSK_inverse(Tableau([]), Tableau([])) [[], []]
Check that
RSK_inverse()
is the inverse ofRSK()
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
-
sage.combinat.rsk.
to_matrix
(t, b)¶ Return the integer matrix corresponding to a two-line array.
INPUT:
t
– The top line of the arrayb
– The bottom line of the array
OUTPUT:
An
-matrix (where
and
are the maximum entries in
and
respectively) whose
-th entry, for any
and
, is the number of all positions
satisfying
and
.
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]