#5551: [with patch, needs review] Permutation from a pair of standard tableaux
---------------------------+------------------------------------------------
Reporter: slabbe | Owner: slabbe
Type: enhancement | Status: assigned
Priority: major | Milestone: sage-3.4.1
Component: combinatorics | Keywords: robinson schensted
---------------------------+------------------------------------------------
Comment(by slabbe):
Dear Florent,
Thanks for your quick answer,
Replying to [comment:3 hivert]:
> Dear Sebastien,
>
> It's good to have this ! Thanks.
Cool!
> There are three little problems:
Did you forget the third one or is this a joke meaning you are of the
second type of mathematician?
>
> 1) The documentation says:
> {{{
> - a pair of two standard tableaux of the same shape.
> The right tableau must be over the integers 1 to n,
> where n is its size.
> }}}
> As far as I know a tableau with entries from 1 to n is what is called a
*standard tableau*.
And increasing in row and column. Right. I agree. I should remove the
second sentence above.
So this leads me to a related question. From a permutation, Robinson-
Schensted Algo gives a pair of standard tableaux :
{{{
sage: p = Permutation([3, 6, 5, 2, 7, 4, 1])
sage: p.robinson_schensted()
[[[1, 4, 7], [2, 5], [3], [6]], [[1, 2, 5], [3, 6], [4], [7]]]
}}}
But from the following "non bijective" permutation, we obtain a pair of
tableaux (p,q) where p is semi-standard and q is standard. Well, we can
say more about p : there are no repeated entry, only possible weigth 1 and
0.
{{{
sage: p = Permutation([3, 6, 5, 2, 117, 4, 1])
sage: p.robinson_schensted()
[[[1, 4, 117], [2, 5], [3], [6]], [[1, 2, 5], [3, 6], [4], [7]]]
sage: t1,t2 = _
sage: t1.weight()
[1, 1, 1, 1, 1, 1, 0, 0, 0, ..., 0, 0, 1]
sage: t2.weight()
[1, 1, 1, 1, 1, 1, 1]
}}}
Should from_tableaux handle the above pair of tableaux? Actually it does :
{{{
sage: p = Permutation([3, 6, 5, 2, 117, 4, 1]) ; p
[3, 6, 5, 2, 117, 4, 1]
sage: import sage.combinat.permutation as permutation
sage: p.robinson_schensted()
[[[1, 4, 117], [2, 5], [3], [6]], [[1, 2, 5], [3, 6], [4], [7]]]
sage: permutation.from_tableaux(*_)
[3, 6, 5, 2, 117, 4, 1]
}}}
Then, what should the input of from_tableaux say? Should it say simply a
pair of standard tableaux as robinson_shensted doc string says it returns
a pair of standard tableaux? Should it say that it handles a pair (p, q)
of tableaux where p is semi-standard (weigth 0 or 1) and q is standard?
> When there are repeated entries the usual terminology is semi standard
tableaux or young
> tableaux. See eg: http://en.wikipedia.org/wiki/Young_diagram
>
>
>
> 2) why not call it {{{robinson_schented_inv}}} ?
>
There is a section in permutation.py containing functions constructing a
permutation from different objects :
{{{
#############################
# Constructing Permutations #
#############################
def from_permutation_group_element(pge):
def from_rank(n, rank):
def from_inversion_vector(iv):
def from_cycles(n, cycles):
def from_lehmer_code(lehmer):
def from_reduced_word(rw):
}}}
The name from_tableaux was then natural. Also, I coded the function for a
colleague used to mathematica and he told me in mathematica they use
{{{TableauxToPermutation}}} and {{{PermutationToTableaux}}}. I don't mind
change it to robinson_schensted_inv or robinson_schensted_inverse(). Do I?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5551#comment:4>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
