Opened 7 years ago

Closed 7 years ago

#13742 closed defect (fixed)

No Permutation should be created that its method cannot handle

Reported by: ncohen Owned by: sage-combinat
Priority: major Milestone: sage-5.6
Component: combinatorics Keywords:
Cc: vdelecroix, hivert, nthiery, dimpase, tscrim 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 dimpase)

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 dimpase 7 years ago.
fix to disallow permutations with cycles of form (x,x)
trac_13742.patch (19.6 KB) - added by ncohen 7 years ago.
trac_13742_reviewer1.patch (3.2 KB) - added by ncohen 7 years ago.
removing some of check_input=False

Download all attachments as: .zip

Change History (28)

comment:1 Changed 7 years ago by ncohen

  • Authors set to Nathann Cohen
  • Status changed from new to needs_review
Last edited 7 years ago by ncohen (previous) (diff)

comment:2 Changed 7 years ago by ncohen

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

comment:3 Changed 7 years ago by ncohen

  • Description modified (diff)

comment:4 Changed 7 years ago by ncohen

  • Description modified (diff)

comment:5 Changed 7 years ago by ncohen

  • Cc vdelecroix hivert nthiery dimpase added

comment:6 Changed 7 years ago by ncohen

  • Description modified (diff)

comment:7 Changed 7 years ago by ncohen

  • Description modified (diff)

comment:8 Changed 7 years ago by dimpase

  • Description modified (diff)
  • Status changed from needs_review to 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 7 years ago by ncohen

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: Changed 7 years ago by ncohen

  • Status changed from needs_info to needs_review

Patch updated !

Nathann

comment:11 in reply to: ↑ 10 Changed 7 years ago by dimpase

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 7 years ago by dimpase

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 7 years ago by dimpase

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

comment:13 Changed 7 years ago by dimpase

  • Description modified (diff)

comment:14 follow-up: Changed 7 years ago by dimpase

  • Status changed from needs_review to 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 in reply to: ↑ 14 Changed 7 years ago by dimpase

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 7 years ago by ncohen

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 7 years ago by ncohen

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 7 years ago by dimpase

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 7 years ago by ncohen

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 7 years ago by ncohen

comment:20 Changed 7 years ago by dimpase

  • Status changed from needs_work to positive_review

comment:21 Changed 7 years ago by tscrim

  • Cc tscrim added

For patchbot:

Apply: trac_13742.patch, trac_13742_reviewer1.patch, general_dihedral_group_fix.patch

comment:22 Changed 7 years ago by jdemeyer

  • Reviewers set to Dmitrii Pasechnik

comment:23 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to 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 7 years ago by ncohen

  • Status changed from needs_work to positive_review

Sorry about that. Patch updated !

Nathann

Changed 7 years ago by ncohen

removing some of check_input=False

comment:25 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.6.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.