#8322: on sage.combinat.tableau.insert_word() , parameter left= is broken (fix
provided)
-----------------------------+----------------------------------------------
Reporter: drini | Owner: somebody
Type: defect | Status: new
Priority: major | Milestone: sage-4.3.3
Component: combinatorics | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
on
/usr/local/sage2/local/lib/python2.6/site-
packages/sage/combinat/tableau.py
at the
{{{
def insert_word():
if left:
w = [i for i in reversed(w)]
res = self
for i in w:
res = res.schensted_insert(i,left=left)
return res
}}}
the left= parameter on insert word has no effect as the following code
shows:
{{{
T=Tableau([])
w = [2,1,1,3,2,4]
print T.insert_word(w)
T=Tableau([])
print T.insert_word(w,left=True)
T=Tableau([])
print T.insert_word(w,left=False)
}}}
printing
{{{
[[1, 1, 2, 4], [2, 3]]
[[1, 1, 2, 4], [2, 3]]
[[1, 1, 2, 4], [2, 3]]
}}}
which is the correct result of right row-insertion for Schensted's
algorithm but left-insertion is broken.
The problem lies on the left=left on the inner call, which should be
'''res = res.schensted_insert(i,left=False) '''
The background is this (ref: William, Fulton. Young Tableaux. Cambridge
University Press)
A "left" insertion a -> b -> c (starting with c)
is equivalent to right insertion a <- b <- c (starting with a)
therefore the lines
{{{
if left:
w = [i for i in reversed(w)]
}}}
are '''correctly transforming''' the left insertion into a right one by
reversing the insertion order .
However, left=left is an error, shoud be left=False since it's already
converted into a right insertion, and so:
setting left=True will exchange the meanings of left-right insertions,
since the reversal already turned the column-insertion into row-insertion
(kind of like "negative-negative" cancelling)
and the result is that calling left=False on insert_word will give the
left result and left=True will give the right one!!
The correct code, therefore is
{{{
def insert_word():
if left:
w = [i for i in reversed(w)]
res = self
for i in w:
res = res.schensted_insert(i,left=False)
return res
}}}
which would give the correct results:
{{{
w = [2,1,1,3,2,4]
T=Tableau([]); print insertar(T, w)
T=Tableau([]); print insertar(T, w,left=False)
T=Tableau([]); print insertar(T, w,left=True)
}}}
(insertar is an alias I made for testing) and would then print:
{{{
[[1, 1, 2, 4], [2, 3]]
[[1, 1, 2, 4], [2, 3]]
[[1, 1, 2], [2, 3], [4]]
}}}
default call : CORRECT (right insertion) [[BR]]
explicit right insertion : CORRECT [[BR]]
explicit left insertion : CORRECT
whereas setting res = res.schensted_insert(i,left=True)
would give
{{{
[[1, 1, 2], [2, 3], [4]]
[[1, 1, 2], [2, 3], [4]]
[[1, 1, 2, 4], [2, 3]]
}}}
default call : left-insertion WRONG! [[BR]]
explicit right insertion : WRONG! (it gave the left one) [[BR]]
explicit left insertion : WRONG! (it gave the right one)
Notice also that setting left=True affects the default case.
'''Conclusion'''
{{{
res = res.schensted_insert(i,left=left)
}}}
should be changed to
{{{
res = res.schensted_insert(i,left=False)
}}}
This is first bug I send, so I apologize if I don't fill correctly the
values below
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8322>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
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.
