Sage: Ticket #13742: No Permutation should be created that its method cannot handle
https://trac.sagemath.org/ticket/13742
<p>
The code from sage.combinat.permutation is very bad. Bad input is never checked, and when ones decides that Permutations are only defined on integers and do not contain 0, bad input happens. The code implicitly assumes that the elements are 1...n despite that, and the robinson_schensted function (no idea of what it does) definitely uses it on something different (i.e. lists, on which no total order is even defined !).
</p>
<p>
This patch was meant to convince me that Sage could be trusted, and after wasting several hours on this I just *DO NOT* trust what is contained in the Combinat branch. It has been explained to me that "the code depends on <a class="missing wiki">CombinatorialObject?</a>? which is deprecated  not as we usually deprecate code, but by comments in its documentation  and that it could not be deprecated formally (with warnings, exceptions, ...) because a lot of people use it." And it seems to have been the case for the last 5 years.
</p>
<p>
Nothing is done to change that. And I will not. This patch is an attempt to convince me that I can use the Permutation class. That is all. It checks stuff, adds warnings everywhere, and documentation.
</p>
<p>
Honestly, it makes me sick to think such a thing is in Sage. That's bad work, period.
</p>
<p>
Two comments :
</p>
<ul><li>For those who want to use the code as before, even when to handle things it is not meant to handle, use check_input=True as a flag when creating a partition Object. And if you NEED to use this, you may as well write the code you need properly. Don't share code that you cannot trust.
</li><li>from_cycles considers that the empty permutation is [], while Permutation([]) is [1]. It does not make any sense. I'm sick of it. This is bad work too. I don't care what people prefer, but please take a decision and stick with it.
</li></ul><p>
Nathann
</p>
<p>
(see also <a class="extlink" href="https://groups.google.com/forum/?fromgroups=#!topic/sagedevel/36Ukvl_Jz2Y"><span class="icon"></span>https://groups.google.com/forum/?fromgroups=#!topic/sagedevel/36Ukvl_Jz2Y</a>)
</p>
<p>
Apply to the Sage library
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13742/trac_13742.patch" title="Attachment 'trac_13742.patch' in Ticket #13742">trac_13742.patch</a><a class="tracrawlink" href="https://trac.sagemath.org/rawattachment/ticket/13742/trac_13742.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13742/trac_13742_reviewer1.patch" title="Attachment 'trac_13742_reviewer1.patch' in Ticket #13742">trac_13742_reviewer1.patch</a><a class="tracrawlink" href="https://trac.sagemath.org/rawattachment/ticket/13742/trac_13742_reviewer1.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13742/general_dihedral_group_fix.patch" title="Attachment 'general_dihedral_group_fix.patch' in Ticket #13742">general_dihedral_group_fix.patch</a><a class="tracrawlink" href="https://trac.sagemath.org/rawattachment/ticket/13742/general_dihedral_group_fix.patch" title="Download"></a>
</li></ul>enusSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/13742
Trac 1.1.6ncohenThu, 22 Nov 2012 14:09:30 GMTstatus changed; author set
https://trac.sagemath.org/ticket/13742#comment:1
https://trac.sagemath.org/ticket/13742#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
TicketncohenThu, 22 Nov 2012 14:11:13 GMT
https://trac.sagemath.org/ticket/13742#comment:2
https://trac.sagemath.org/ticket/13742#comment:2
<p>
(I removed a doctest in schubert_polynomial because it is not necessary anymore)
</p>
TicketncohenThu, 22 Nov 2012 14:15:03 GMTdescription changed
https://trac.sagemath.org/ticket/13742#comment:3
https://trac.sagemath.org/ticket/13742#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13742?action=diff&version=3">diff</a>)
</li>
</ul>
TicketncohenThu, 22 Nov 2012 14:15:53 GMTdescription changed
https://trac.sagemath.org/ticket/13742#comment:4
https://trac.sagemath.org/ticket/13742#comment:4
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13742?action=diff&version=4">diff</a>)
</li>
</ul>
TicketncohenThu, 22 Nov 2012 14:22:32 GMTcc set
https://trac.sagemath.org/ticket/13742#comment:5
https://trac.sagemath.org/ticket/13742#comment:5
<ul>
<li><strong>cc</strong>
<em>vdelecroix</em> <em>hivert</em> <em>nthiery</em> <em>dimpase</em> added
</li>
</ul>
TicketncohenThu, 22 Nov 2012 14:24:11 GMTdescription changed
https://trac.sagemath.org/ticket/13742#comment:6
https://trac.sagemath.org/ticket/13742#comment:6
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13742?action=diff&version=6">diff</a>)
</li>
</ul>
TicketncohenThu, 22 Nov 2012 14:43:07 GMTdescription changed
https://trac.sagemath.org/ticket/13742#comment:7
https://trac.sagemath.org/ticket/13742#comment:7
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13742?action=diff&version=7">diff</a>)
</li>
</ul>
TicketdimpaseFri, 23 Nov 2012 17:32:52 GMTstatus, description changed
https://trac.sagemath.org/ticket/13742#comment:8
https://trac.sagemath.org/ticket/13742#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/13742?action=diff&version=8">diff</a>)
</li>
</ul>
<p>
Hi Nathann, why do you insert <code>check_input = False</code> into several examples?
IMHO one example like that should suffice.
</p>
<p>
Why do you have <code>check_input = False</code> in
in <code>b/sage/combinat/integer_vector_weighted.py</code>? Is it because it fails otherwise?
There is also a typo in line 6 of this file, please fix.
</p>
TicketncohenFri, 23 Nov 2012 19:44:24 GMT
https://trac.sagemath.org/ticket/13742#comment:9
https://trac.sagemath.org/ticket/13742#comment:9
<p>
Indeed, it is because those examples fail otherwise. Why do you say "one such example should suffice" ? You want to remove examples from different files ? Or do you talk about the examples I added myself in the constructor itself ?
</p>
<p>
Anyway, I did something very simple : make the modification needed, then ran the tests. Those which failed got a <code></code>check_input = False<code></code>, and as some failed because they multiplied partitions I also added a flag there. Of course, all should be removed. But this patch is about saving new bugs, not fixing those that have been here for years. Besides, it requires technical knowledge that I do not have.
</p>
<p>
Nathann
</p>
TicketncohenFri, 23 Nov 2012 19:45:30 GMTstatus changed
https://trac.sagemath.org/ticket/13742#comment:10
https://trac.sagemath.org/ticket/13742#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Patch updated !
</p>
<p>
Nathann
</p>
TicketdimpaseSat, 24 Nov 2012 05:33:18 GMT
https://trac.sagemath.org/ticket/13742#comment:11
https://trac.sagemath.org/ticket/13742#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13742#comment:10" title="Comment 10">ncohen</a>:
typo;
</p>
<pre class="wiki">diff git a/sage/combinat/permutation.py b/sage/combinat/permutation.py
 a/sage/combinat/permutation.py
+++ b/sage/combinat/permutation.py
@@ 12,7 +12,7 @@
:trac:`13742`). This is dangerous. In particular, the
:meth:`Permutation_class._left_to_right_multiply_on_right` method (which can
be called trough multiplication) disables the input checks (see
 :method:`Permutation`). This should not happen. Do not trust the results.
+ :meth:`Permutation`). This should not happen. Do not trust the results.
AUTHORS:
</pre><p>
I know the reason behind the weirdness in <code>sage/combinat/integer_vector_weighted.py</code>. Namely, the <code>list()</code> converts the list of list of integers into a list of (invalid) permutations, i.e 0 and repeated entries are allowed. The need for this is lost to me.
I've applied the following patch, and now try to run the tests to see if something fails.
</p>
<pre class="wiki">diff git a/sage/combinat/integer_vector_weighted.py b/sage/combinat/integer_vector_weighted.py
 a/sage/combinat/integer_vector_weighted.py
+++ b/sage/combinat/integer_vector_weighted.py
@@ 163,5 +163,4 @@
perm = Word(self.weight).standard_permutation()
l = [x for x in sorted(self.weight)]
 return [perm._left_to_right_multiply_on_right(Permutation_class(x, check_input = False)) for x in self._recfun(self.n,l)]

+ return [perm.action(_) for _ in self._recfun(self.n,l)]
</pre>
TicketdimpaseSat, 24 Nov 2012 08:45:18 GMT
https://trac.sagemath.org/ticket/13742#comment:12
https://trac.sagemath.org/ticket/13742#comment:12
<p>
In the attached patch I've cleaned up <code>combinat/integer_vector_weighted.py</code> which was making permutations from anything that crawls, and also removed some, although not all, <code>check_input=False</code> from <code>combinat/permutation.py</code>.
</p>
<p>
One has to decide what to do with RobinsonSchensted. As it can be applied to nonpermutations, it must leave the Permutation class and get a real place somewhere. This would allow a good cleanup of <code>combinat/permutation.py</code>.
</p>
<p>
</p>
TicketdimpaseSat, 24 Nov 2012 09:28:01 GMTattachment set
https://trac.sagemath.org/ticket/13742
https://trac.sagemath.org/ticket/13742
<ul>
<li><strong>attachment</strong>
set to <em>general_dihedral_group_fix.patch</em>
</li>
</ul>
<p>
fix to disallow permutations with cycles of form (x,x)
</p>
TicketdimpaseSat, 24 Nov 2012 09:30:45 GMTdescription changed
https://trac.sagemath.org/ticket/13742#comment:13
https://trac.sagemath.org/ticket/13742#comment:13
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13742?action=diff&version=13">diff</a>)
</li>
</ul>
TicketdimpaseSat, 24 Nov 2012 12:19:57 GMTstatus changed
https://trac.sagemath.org/ticket/13742#comment:14
https://trac.sagemath.org/ticket/13742#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
in the <a class="extlink" href="http://patchbot.sagemath.org/log/13742/Fedora/17/x86_64/3.6.61.fc17.x86_64/volkerdesktop.stp.dias.ie/20121124%2009:53:37%20+0000?short"><span class="icon"></span>output of Volker's patchbot</a> you will see
</p>
<pre class="wiki">sage t force_lib devel/sage13742/sage/graphs/comparability.pyx
[?1034h**********************************************************************
File "/mnt/storage2TB/patchbot/Sage/sage5.5.rc0/devel/sage13742/sage/graphs/comparability.pyx", line 610:
sage: p1, p2 = map(Permutation, perm)
Exception raised:
Traceback (most recent call last):
File "/mnt/storage2TB/patchbot/Sage/sage5.5.rc0/local/bin/ncadoctest.py", line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/mnt/storage2TB/patchbot/Sage/sage5.5.rc0/local/bin/sagedoctest.py", line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
File "/mnt/storage2TB/patchbot/Sage/sage5.5.rc0/local/bin/ncadoctest.py", line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_5[8]>", line 1, in <module>
p1, p2 = map(Permutation, perm)###line 610:
sage: p1, p2 = map(Permutation, perm)
File "/mnt/storage2TB/patchbot/Sage/sage5.5.rc0/local/lib/python/sitepackages/sage/combinat/permutation.py", line 296, in Permutation
return Permutation_class(l, check_input = check_input)
File "/mnt/storage2TB/patchbot/Sage/sage5.5.rc0/local/lib/python/sitepackages/sage/combinat/permutation.py", line 339, in __init__
raise ValueError("The elements must be strictly positive integers.")
ValueError: The elements must be strictly positive integers.
**********************************************************************
</pre><p>
(and, in fact, there are 0s there, the permutations are permuting numbers from 0 to n1 rather than from 1 to n there.)
</p>
<p>
Also, in <code>sage.graphs.comparability</code> the function is_permutation does not fly together with Permutation.
</p>
TicketdimpaseSat, 24 Nov 2012 12:41:07 GMT
https://trac.sagemath.org/ticket/13742#comment:15
https://trac.sagemath.org/ticket/13742#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13742#comment:14" title="Comment 14">dimpase</a>:
</p>
<pre class="wiki">diff git a/sage/graphs/comparability.pyx b/sage/graphs/comparability.pyx
 a/sage/graphs/comparability.pyx
+++ b/sage/graphs/comparability.pyx
@@ 607,7 +607,8 @@
Plotting the realization as an intersection graph of segments::
sage: true, perm = is_permutation(g, certificate = True)
 sage: p1, p2 = map(Permutation, perm)
+ sage: p1 = Permutation([nn+1 for nn in perm[0]])
+ sage: p2 = Permutation([nn+1 for nn in perm[1]])
sage: p = p2 * p1.inverse()
sage: p.show(representation = "braid")
</pre><p>
makes the tests pass. But probably more needs to be done...
</p>
TicketncohenSat, 24 Nov 2012 12:59:59 GMT
https://trac.sagemath.org/ticket/13742#comment:16
https://trac.sagemath.org/ticket/13742#comment:16
<p>
Ahahah. Well, I wrote this file, so for a change I can deal with stuff I know instead of having to guess.. Give me a few minutes !
</p>
<p>
Nathann
</p>
TicketncohenSat, 24 Nov 2012 13:09:17 GMT
https://trac.sagemath.org/ticket/13742#comment:17
https://trac.sagemath.org/ticket/13742#comment:17
<p>
Hello again ! Well, actually your fix is sufficient, so I included it inside of my patch, which I just updated. This code is meant to return a permutation on the elements of the graph, and it does so as a list.. Unless somebody who does not use this code as I do thinks otherwise, I think that it is better to return lists of vertices, as the functions currently do, which may be integers or anything else... Hence the code does not needto be modified, and your docstring fix is sufficient !
</p>
<p>
Thanks !
</p>
TicketdimpaseSat, 24 Nov 2012 13:40:32 GMT
https://trac.sagemath.org/ticket/13742#comment:18
https://trac.sagemath.org/ticket/13742#comment:18
<p>
another thing: one can still create a "permutation" which is not a permutation, and get an error:
</p>
<pre class="wiki">sage: p=Permutation([3,4,5,1])
sage: p.is_even()

IndexError Traceback (most recent call last)
/usr/local/src/sage/sage5.5.rc0/devel/sagemain/<ipython console> in <module>()
/usr/local/src/sage/sage5.5.rc0/local/lib/python2.7/sitepackages/sage/combinat/permutation.pyc in is_even(self)
859 """
860
> 861 if self.signature() == 1:
862 return True
863 else:
/usr/local/src/sage/sage5.5.rc0/local/lib/python2.7/sitepackages/sage/combinat/permutation.pyc in signature(p)
842 1
843 """
> 844 return (1)**(len(p)len(p.to_cycles()))
845
846 #one can also use sign as an alias for signature
/usr/local/src/sage/sage5.5.rc0/local/lib/python2.7/sitepackages/sage/combinat/permutation.pyc in to_cycles(self, singletons)
652 while next != cycleFirst:
653 cycle.append( next )
> 654 l[next  1], next = False, l[next  1]
655 #Add the cycle to the list of cycles
656 if singletons or len(cycle) > 1:
IndexError: list index out of range
</pre><p>
(many other functions of p will error out, too)
Any plans to deal with this?
</p>
TicketncohenSat, 24 Nov 2012 14:02:45 GMT
https://trac.sagemath.org/ticket/13742#comment:19
https://trac.sagemath.org/ticket/13742#comment:19
<p>
Well, we can check that if the input is a list, then it has size n, can't we ? With the patch we already check that no element appears twice. I updated the patch again, and this is now checked too.
</p>
<p>
Note that this made method <code></code>from_major_code<code></code> raise Exceptions, as it builds things like Permutation([9]). I added <code>check_input = False</code> inside of it, but it still checks the Permutation is returns. I also added a warning.
</p>
<p>
Nathann
</p>
TicketncohenSat, 24 Nov 2012 14:03:42 GMTattachment set
https://trac.sagemath.org/ticket/13742
https://trac.sagemath.org/ticket/13742
<ul>
<li><strong>attachment</strong>
set to <em>trac_13742.patch</em>
</li>
</ul>
TicketdimpaseSun, 25 Nov 2012 10:51:47 GMTstatus changed
https://trac.sagemath.org/ticket/13742#comment:20
https://trac.sagemath.org/ticket/13742#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
TickettscrimSun, 25 Nov 2012 17:58:16 GMTcc changed
https://trac.sagemath.org/ticket/13742#comment:21
https://trac.sagemath.org/ticket/13742#comment:21
<ul>
<li><strong>cc</strong>
<em>tscrim</em> added
</li>
</ul>
<p>
For patchbot:
</p>
<p>
Apply: trac_13742.patch, trac_13742_reviewer1.patch, general_dihedral_group_fix.patch
</p>
TicketjdemeyerSun, 16 Dec 2012 16:13:04 GMTreviewer set
https://trac.sagemath.org/ticket/13742#comment:22
https://trac.sagemath.org/ticket/13742#comment:22
<ul>
<li><strong>reviewer</strong>
set to <em>Dmitrii Pasechnik</em>
</li>
</ul>
TicketjdemeyerMon, 17 Dec 2012 07:34:45 GMTstatus changed
https://trac.sagemath.org/ticket/13742#comment:23
https://trac.sagemath.org/ticket/13742#comment:23
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
There are some documentation errors:
</p>
<pre class="wiki">/release/merger/sage5.6.beta0/local/lib/python2.7/sitepackages/sage/combinat/permutation.py:docstring of sage.combinat.permutation:1: ERROR: Content block expected for the "WARNING" directive; none found.
/release/merger/sage5.6.beta0/local/lib/python2.7/sitepackages/sage/combinat/permutation.py:docstring of sage.combinat.permutation:1: ERROR: Content block expected for the "WARNING" directive; none found.
</pre>
TicketncohenMon, 17 Dec 2012 11:03:05 GMTstatus changed
https://trac.sagemath.org/ticket/13742#comment:24
https://trac.sagemath.org/ticket/13742#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
Sorry about that. Patch updated !
</p>
<p>
Nathann
</p>
TicketncohenMon, 17 Dec 2012 11:03:18 GMTattachment set
https://trac.sagemath.org/ticket/13742
https://trac.sagemath.org/ticket/13742
<ul>
<li><strong>attachment</strong>
set to <em>trac_13742_reviewer1.patch</em>
</li>
</ul>
<p>
removing some of check_input=False
</p>
TicketjdemeyerFri, 21 Dec 2012 09:33:10 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/13742#comment:25
https://trac.sagemath.org/ticket/13742#comment:25
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage5.6.beta1</em>
</li>
</ul>
Ticket