No Permutation should be created that its method cannot handle

[ncohen]

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

• trac_13742.patch​
• trac_13742_reviewer1.patch​
• general_dihedral_group_fix.patch​

[ncohen]

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 check 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

[ncohen]

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

[dimpase]

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.

[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

[ncohen]

Patch updated !

Nathann

[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)]

[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.

[dimpase]

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

[dimpase]

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.

[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...

[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

[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 !

[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?

[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

[tscrim]

For patchbot:

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

[jdemeyer]

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.

[ncohen]

Sorry about that. Patch updated !

Nathann

[ncohen]

removing some of check_input=False