Opened 10 years ago
Closed 10 years ago
#13742 closed defect (fixed)
No Permutation should be created that its method cannot handle
Reported by: | Nathann Cohen | Owned by: | Sage Combinat CC user |
---|---|---|---|
Priority: | major | Milestone: | sage-5.6 |
Component: | combinatorics | Keywords: | |
Cc: | Vincent Delecroix, Florent Hivert, Nicolas M. Thiéry, Dima Pasechnik, Travis Scrimshaw | Merged in: | sage-5.6.beta1 |
Authors: | Nathann Cohen | Reviewers: | Dmitrii Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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 !).
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 CombinatorialObject?? 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.
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.
Honestly, it makes me sick to think such a thing is in Sage. That's bad work, period.
Two comments :
- 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.
- 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.
Nathann
(see also https://groups.google.com/forum/?fromgroups=#!topic/sage-devel/36Ukvl_Jz2Y)
Apply to the Sage library
Attachments (3)
Change History (28)
comment:1 Changed 10 years ago by
Authors: | → Nathann Cohen |
---|---|
Status: | new → needs_review |
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:4 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:5 Changed 10 years ago by
Cc: | Vincent Delecroix Florent Hivert Nicolas M. Thiéry Dima Pasechnik added |
---|
comment:6 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:7 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:8 Changed 10 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_review → needs_info |
Hi Nathann, why do you insert check_input = False
into several examples?
IMHO one example like that should suffice.
Why do you have check_input = False
in
in b/sage/combinat/integer_vector_weighted.py
? Is it because it fails otherwise?
There is also a typo in line 6 of this file, please fix.
comment:9 Changed 10 years ago by
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 ?
Anyway, I did something very simple : make the modification needed, then ran the tests. Those which failed got a check_input = False
, 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.
Nathann
comment:10 follow-up: 11 Changed 10 years ago by
Status: | needs_info → needs_review |
---|
Patch updated !
Nathann
comment:11 Changed 10 years ago by
Replying to ncohen: typo;
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:
I know the reason behind the weirdness in sage/combinat/integer_vector_weighted.py
. Namely, the list()
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.
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)]
comment:12 Changed 10 years ago by
In the attached patch I've cleaned up combinat/integer_vector_weighted.py
which was making permutations from anything that crawls, and also removed some, although not all, check_input=False
from combinat/permutation.py
.
One has to decide what to do with Robinson-Schensted. As it can be applied to non-permutations, it must leave the Permutation class and get a real place somewhere. This would allow a good cleanup of combinat/permutation.py
.
Changed 10 years ago by
Attachment: | general_dihedral_group_fix.patch added |
---|
fix to disallow permutations with cycles of form (x,x)
comment:13 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:14 follow-up: 15 Changed 10 years ago by
Status: | needs_review → needs_work |
---|
in the output of Volker's patchbot you will see
sage -t -force_lib devel/sage-13742/sage/graphs/comparability.pyx [?1034h********************************************************************** File "/mnt/storage2TB/patchbot/Sage/sage-5.5.rc0/devel/sage-13742/sage/graphs/comparability.pyx", line 610: sage: p1, p2 = map(Permutation, perm) Exception raised: Traceback (most recent call last): File "/mnt/storage2TB/patchbot/Sage/sage-5.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/sage-5.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/sage-5.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/sage-5.5.rc0/local/lib/python/site-packages/sage/combinat/permutation.py", line 296, in Permutation return Permutation_class(l, check_input = check_input) File "/mnt/storage2TB/patchbot/Sage/sage-5.5.rc0/local/lib/python/site-packages/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. **********************************************************************
(and, in fact, there are 0s there, the permutations are permuting numbers from 0 to n-1 rather than from 1 to n there.)
Also, in sage.graphs.comparability
the function is_permutation does not fly together with Permutation.
comment:15 Changed 10 years ago by
Replying to dimpase:
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")
makes the tests pass. But probably more needs to be done...
comment:16 Changed 10 years ago by
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 !
Nathann
comment:17 Changed 10 years ago by
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 !
Thanks !
comment:18 Changed 10 years ago by
another thing: one can still create a "permutation" which is not a permutation, and get an error:
sage: p=Permutation([3,4,5,1]) sage: p.is_even() --------------------------------------------------------------------------- IndexError Traceback (most recent call last) /usr/local/src/sage/sage-5.5.rc0/devel/sage-main/<ipython console> in <module>() /usr/local/src/sage/sage-5.5.rc0/local/lib/python2.7/site-packages/sage/combinat/permutation.pyc in is_even(self) 859 """ 860 --> 861 if self.signature() == 1: 862 return True 863 else: /usr/local/src/sage/sage-5.5.rc0/local/lib/python2.7/site-packages/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/sage-5.5.rc0/local/lib/python2.7/site-packages/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
(many other functions of p will error out, too) Any plans to deal with this?
comment:19 Changed 10 years ago by
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.
Note that this made method from_major_code
raise Exceptions, as it builds things like Permutation([9]). I added
check_input = False
inside of it, but it still checks the Permutation is returns. I also added a warning.
Nathann
Changed 10 years ago by
Attachment: | trac_13742.patch added |
---|
comment:20 Changed 10 years ago by
Status: | needs_work → positive_review |
---|
comment:21 Changed 10 years ago by
Cc: | Travis Scrimshaw added |
---|
For patchbot:
Apply: trac_13742.patch, trac_13742_reviewer1.patch, general_dihedral_group_fix.patch
comment:22 Changed 10 years ago by
Reviewers: | → Dmitrii Pasechnik |
---|
comment:23 Changed 10 years ago by
Status: | positive_review → needs_work |
---|
There are some documentation errors:
/release/merger/sage-5.6.beta0/local/lib/python2.7/site-packages/sage/combinat/permutation.py:docstring of sage.combinat.permutation:1: ERROR: Content block expected for the "WARNING" directive; none found. /release/merger/sage-5.6.beta0/local/lib/python2.7/site-packages/sage/combinat/permutation.py:docstring of sage.combinat.permutation:1: ERROR: Content block expected for the "WARNING" directive; none found.
comment:24 Changed 10 years ago by
Status: | needs_work → positive_review |
---|
Sorry about that. Patch updated !
Nathann
Changed 10 years ago by
Attachment: | trac_13742_reviewer1.patch added |
---|
removing some of check_input=False
comment:25 Changed 10 years ago by
Merged in: | → sage-5.6.beta1 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
(I removed a doctest in schubert_polynomial because it is not necessary anymore)