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
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 [Sta1999].
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 type 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
and
both
exist in row
, we only set
and continue.
INPUT:
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 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
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
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 [Sta1999].
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 type 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
and
both
exist in row
, we only set
and continue.
INPUT:
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 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
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 -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]