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:

Status badges

Description (last modified by Dima Pasechnik)

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)

general_dihedral_group_fix.patch (1.7 KB) - added by Dima Pasechnik 10 years ago.
fix to disallow permutations with cycles of form (x,x)
trac_13742.patch (19.6 KB) - added by Nathann Cohen 10 years ago.
trac_13742_reviewer1.patch (3.2 KB) - added by Nathann Cohen 10 years ago.
removing some of check_input=False

Download all attachments as: .zip

Change History (28)

comment:1 Changed 10 years ago by Nathann Cohen

Authors: Nathann Cohen
Status: newneeds_review
Last edited 10 years ago by Nathann Cohen (previous) (diff)

comment:2 Changed 10 years ago by Nathann Cohen

(I removed a doctest in schubert_polynomial because it is not necessary anymore)

comment:3 Changed 10 years ago by Nathann Cohen

Description: modified (diff)

comment:4 Changed 10 years ago by Nathann Cohen

Description: modified (diff)

comment:5 Changed 10 years ago by Nathann Cohen

Cc: Vincent Delecroix Florent Hivert Nicolas M. Thiéry Dima Pasechnik added

comment:6 Changed 10 years ago by Nathann Cohen

Description: modified (diff)

comment:7 Changed 10 years ago by Nathann Cohen

Description: modified (diff)

comment:8 Changed 10 years ago by Dima Pasechnik

Description: modified (diff)
Status: needs_reviewneeds_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 Nathann Cohen

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 Changed 10 years ago by Nathann Cohen

Status: needs_infoneeds_review

Patch updated !

Nathann

comment:11 in reply to:  10 Changed 10 years ago by Dima Pasechnik

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 Dima Pasechnik

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 Dima Pasechnik

fix to disallow permutations with cycles of form (x,x)

comment:13 Changed 10 years ago by Dima Pasechnik

Description: modified (diff)

comment:14 Changed 10 years ago by Dima Pasechnik

Status: needs_reviewneeds_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 in reply to:  14 Changed 10 years ago by Dima Pasechnik

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 Nathann Cohen

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 Nathann Cohen

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 Dima Pasechnik

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 Nathann Cohen

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 Nathann Cohen

Attachment: trac_13742.patch added

comment:20 Changed 10 years ago by Dima Pasechnik

Status: needs_workpositive_review

comment:21 Changed 10 years ago by Travis Scrimshaw

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 Jeroen Demeyer

Reviewers: Dmitrii Pasechnik

comment:23 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_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 Nathann Cohen

Status: needs_workpositive_review

Sorry about that. Patch updated !

Nathann

Changed 10 years ago by Nathann Cohen

Attachment: trac_13742_reviewer1.patch added

removing some of check_input=False

comment:25 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.6.beta1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.