Remove CombinatorialClass from Permutations

[tscrim]

Part of #12913.

---

Apply: trac_14772-remove_cc_permutations-ts.patch​

[tscrim]

Minor dependency on #8386 due to use of Permutation_class.

[tscrim]

Let's try it with #14519 as a dependency.

[mhansen]

Looks good to me. The main issue is that there are two classcall_private methods with out tests; however, they are tested in the the doctest for init. I don't think it makes sense to duplicate the tests. Maybe just a note that it is tested via the init doctests?

[tscrim]

I added some (simple) doctests to the __classcall_private__() functions.

[tscrim]

All doctest errors should be fixed now.

[darij]

This conflicts with #14808 again. Travis, could you update #14808 please? Thank you.

[tscrim]

I put this over #14808, so I'm putting that as a dependency now.

[darij]

It'll probably need some rebase, though.

[tscrim]

I already had #14808 applied in the combinat queue, so it shouldn't need rebasing.

[darij]

OOPS, you're right. Sorry; I had an obsolete patch in my .hg/patches folder.

[darij]

But the number_of_inversions(self) docstring is still unfixed, or am I totally wrong about it?

[tscrim]

@@ -1542,10 +1561,10 @@ class Permutation_class(CombinatorialObj
 
     def number_of_inversions(self):
         r"""
-        Returns the number of inversions in the permutation p.
-
-        An inversion of a permutation is a pair of elements (p[i],p[j])
-        with i < j and p[i] > p[j].
+        Return the number of inversions in ``self``.
+
+        An inversion of a permutation is a pair of elements `(p_i,p_j)`
+        with `i < j` and `p_i > p_j`.
 
         REFERENCES:
 

[darij]

I wasn't speaking about the syntax. It should say "a pair of elements (i, j)", not "a pair of elements (p_i, p_j)", so as not to confuse the reader about the output of the inversions() method.

[tscrim]

Ah. Fixed. I also added some latex options for permutations and being able to display them as words (which is how I generally look at them, transpositions on positions). I made some other minor changes to other docstrings I noticed, so I apologize in advance if you have to rebase.

[tscrim]

With the following patches applied on 5.11.beta3

tscrim@as96:~/sage-5.11.beta3/devel/sage-combinat/sage/combinat$ sage -hg qapplied
trac_14610-LSenergy-ms.patch
trac9107_nesting_nested_classes.patch
trac_9107_fix_cross_reference.patch
trac_13589-categories-c3_under_control-nt.patch
trac_14714_latex_dyckword_fix.patch
trac_14748_deprecationwarning.patch
trac_14748_doctest.patch
trac_14748-review-ts.patch
trac_14787-gyw_stats-bs.patch
trac_14762-fix_ASM_ne-ts.patch
trac_12940_affine_permutations-td.patch
trac_14573-path_realizations-ts.patch
trac_14507-tropical_semiring-ts.patch
trac_11407-list_clone_improve-fh.patch
trac_14516-crystals_speedup-ts.patch
trac_7983-major_index_and_other_tableau_fixes-dg.patch
trac_7983-review-ts.patch
trac_12882-matrix_as_dynkin_diagram-ts.patch
trac_14722-lazy_import_at_startup-nt.patch
trac_8386_really_just_moving-fc.patch
trac_8386_big_clean_fc.patch
trac_8386_assert_removal.patch
trac_14808-recoils_of_permutations-ts.patch
trac_10630-vector_partition-ap.patch
trac_14870-fix_int_mod_QQ-ts.patch
trac_14882-backtrack_longtime-dg.patch
trac_14469_repr_graphics.patch
trac_14519-cynthonize_element_wrapper-ts.patch
trac_12250-ktableaux-as.patch
trac_14776-strong-ktableaux-mz.patch
trac_14772-remove_cc_permutations-ts.patch

I cannot reproduce the doctest failure from the patchbot

tscrim@as96:~/sage-5.11.beta3/devel/sage-combinat/sage/combinat$ sage -tp --long combinat.py
Running doctests with ID 2013-07-13-19-05-23-2a0e8ee8.
Doctesting 1 file using 2 threads.
sage -t --long combinat.py
    [428 tests, 6.61 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 6.9 seconds
    cpu time: 2.4 seconds
    cumulative wall time: 6.6 seconds

Only #12250 and #14476 do not have a positive review and this commutes with those patches. So I don't know why that doctest is failing for the patchbot...

[darij]

Looks like MRO. The class Arrangements inherits from Permutations. Permutations of a multiset have their own cardinality() method, which gives the (wrong) 1260 answer in this case. The correct 22 answer is obtained by the standard cardinality() method of FiniteEnumeratedSets? (?) which just takes the length of the list().

[tscrim]

Strange that it wasn't showing up when I was running my doctests (although it did appear when I did it in sage). Typically I get the other behavior. Fixed. Thank Darij.

[tscrim]

Mike, do you think you could do a re-review of this patch? Thanks.

[tscrim]

Darij, since Mike hasn't responding, do you think you could do the final review of this patch? Thanks.

[darij]

I've started the review -- but I'm stuck at PermutationOptions now. You have these doctests:

    EXAMPLES::
    
        sage: p213 = Permutation([2,1,3])
        sage: p312 = Permutation([3,1,2])
        sage: PermutationOptions(mult='l2r', display='list')
        sage: po = PermutationOptions()
        sage: po['display']
        'list'
        sage: p213
        [2, 1, 3]
        sage: PermutationOptions(display='cycle')
        sage: p213
        (1,2)
        sage: PermutationOptions(display='singleton')
        sage: p213
        (1,2)(3)
        sage: PermutationOptions(display='list')

But when I try to run them ingame, they don't behave that nicely:

sage:         sage: p213 = Permutation([2,1,3])
sage:         sage: p312 = Permutation([3,1,2])
sage:         sage: PermutationOptions(mult='l2r', display='list')
sage:         sage: po = PermutationOptions()
Current options for permutations
  - display:        list
  - generator_name: s
  - latex:          list
  - mult:           l2r
sage:         sage: po['display']
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-49-b0a2d723e60c> in <module>()
----> 1 po['display']

TypeError: 'NoneType' object has no attribute '__getitem__'

I have a feeling that they are not recognized as doctests due to the weird place they're in... And I don't know what to do about this.

[tscrim]

Ack...I forgot to check the global options tests. That syntax is from the old sytle, it should be Permutations.global_options. I'll fix them.

You're also correct in that the doctest framework does not pick up dynamically created docstrings (unfortunately).

Thanks,
Travis

[tscrim]

I've made the fixes, but I can't upload it due to the filesize (the limit has been lowered to 256kB on the new server). I've asked Andrew Ohana to see if he can raise that limit a bit. If not, I'll split the patch and reupload.

Best,
Travis

[tscrim]

Okay, here's the new version.

[darij]

In case noone disagrees, I'll remove the "like composition of functions" from this:

  * "l2r" -- left to right like composition of functions (p_1  *
    p_2)(x) = p_2(p_1(x))

because it's extremely misleading. Of course, the whole idea of global variables for this is bad, but that's for a later ticket.

[darij]

Sorry for the spam but I'll be updating this thread with anything potentially controversial I'm doing in my review patch.

The latex method for permutations in reduced-word notation returns an empty string when the permutation is id. I'll replace this by a "1".

[tscrim]

How about 'e' or the empty set instead as to avoid potential conflicts? Or better yet, add a global option about that.

[darij]

You mean an additional one, or allow several different values for the "latex" option?

(On another note: You have changed a "spam.eggs.blah.method(x)" pattern to "from spam.eggs.blah import method; method(x)" pattern several times; is that an example I should follow in my code?)

[tscrim]

I mean add 1 additional global option of the form latex_identity_word which will follow the latex_diagram_str global option in partition.py.

(I think this pattern leads to more readable code; although it seems to make circular imports more prone to breaking.)

[darij]

I've done that change -- feel free to comment.

In other news, Sage doesn't consider the empty permutation to avoid [1]. Do we consider this a bug? (The chances of being bitten by this are nigh 0.)

[zabrocki]

Hi Darij, Can you clarify what you mean? Permutation([]).avoids([1]) returns True for me. If that were not the case, I would consider that a bug.

[darij]

Oh, but:

sage: Permutations(0, avoiding=[1]).list()
[]
sage: Permutations(0, avoiding=[1,2]).list()
[[]]
sage: Permutations(0, avoiding=[1,2,3,4,5]).list()
#doesn't terminate

I guess this is a backtrack.py issue...

[darij]

Should I fix this bug:

sage: S = Permutations(['c','a'])
sage: elt = S(['c','c','c'])
sage: elt in S
True

or is it used in some other files to hack around permutations restrictions similarly to how we use(d?) nonstandard permutations?

[tscrim]

Replying to darij:

Should I fix this bug:

sage: S = Permutations(['c','a'])
sage: elt = S(['c','c','c'])
sage: elt in S
True

or is it used in some other files to hack around permutations restrictions similarly to how we use(d?) nonstandard permutations?

I think it should be fixed. I suspect it's something I introduced... (especially in that case)

I also can't reproduce the avoidance part:

sage: [] in Permutations(0, avoiding=[1])
True
sage: [] in Permutations(avoiding=[1])   
True

but the backtrack error is something that should be fixed. I'll see if I can do it in a few lines, otherwise I'll say push it to another ticket.

[darij]

I tried this change to the check element method of class Permutations_set:

@@ -3845,10 +3879,20 @@ class Permutations_mset(Permutations):
                 sage: S = Permutations(['c','a','c'])
                 sage: elt = S(['c','c','a'])
                 sage: elt.check()
+                sage: elt2 = S(['c','c','c'])
+                Traceback (most recent call last):
+                ...
+                ValueError: Invalid permutation
             """
             mset = self.parent().mset
+            selfdict = {}
             for val in self:
-                if val not in mset:
+                if val in selfdict:
+                    selfdict[val] += 1
+                else:
+                    selfdict[val] = 1
+            for (val, mult) in selfdict.items():
+                if mult != mset.count(val):
                     raise ValueError("Invalid permutation")
 
     def _repr_(self):

But this breaks various doctests since apparently the same check method is used for permutations of length k. I have reverted that change for now.

If you ask me, it is a stupid idea to have permutations of length k inherit from permutations anyway...

[tscrim]

Permutations is suppose to be a common abstract base class for all permutations (in some way it models the category of all types of permutations), so having permutations of length k inherit from it makes sense. However I think we need to implement a stronger __contains__() for the non-standard permutations, perhaps a stupid return x in list(self) (which, somewhat surprisingly to me, the category of FiniteEnumeratedSets does not provide by default).

Also, to fix the backtracker issue, what needs to be done is some simple corner case checking in the __iter__ methods for n == 0. Only if n > 0 do you call PatternAvoider.

Best,
Travis

[darij]

I'm getting SyntaxError: 'return' with argument inside generator when I try to fix this. Can you fix that one?

[darij]

(The review patch I just uploaded includes this error -- feel free to directly edit my review patch rather than your base patch. Maybe you could fix your multiset permutation bug while we're at that, or shadow the check method in the appropriate classes so that my fix won't break other things. I hate to admit but I still don't see through the logic of the various classes defined in permutation.py.

I won't return to this ticket in the next 3 or so hours.)

[tscrim]

I can't reupload over your review patch. Is it okay if I just fold it in to the main one?

[darij]

Yes, that's OK (as long as you look over my review patch, too -- there are some things in it that might need reviewing, in turn). Thanks a lot!

(The code I commented out -- #l[pos_im1] = i-1 and similar -- was just doing nothing.)

[tscrim]

I hacked around it:

if n > 0:
    return iter(PatternAvoider(self, self._p))
return iter([self.element_class(self, [])])

it's a python issue that putting a yield in the function makes it into a generator, which can't return anything at all, including iterators. This makes sense because python a priori doesn't know that it will be an iterator; plus the can of worms whether it should continue the iteration from that point with that iterator.

All combined and back to you Darij.

[tscrim]

For patchbot:

Apply: trac_14772-remove_cc_permutations-ts.patch

[darij]

Great!

I'll look into the multisets issue, but as for now here is a fix for another bug:

sage: Permutations(descents=[1,3,4]).list()

gave an error. It turns out that, lacking an n-value in the input, the code would automatically set n to be the maximum entry of the list [1, 3, 4] plus 1 (btw, that causes another bug when the list is empty; fixed as well), but whoever wrote that must have missed the fact that the positions start with 0 (so a presence of 3 in the list really means that the permutations will have a descent at 4, i. e., their value at 4 will be larger than their value at 5), so the "correct" n would be the maximum entry of the list [1, 3, 4] plus 2. I think this is a completely stupid convention to make, and the syntax (giving the set of descents as a list without the n, having Sage automatically choose the n) should not be supported (no doctests in permutation.py use this syntax). Note that it only allows constructing permutations where the penultimate position is a descent; all the others require the long syntax with the n given! Also, it is misleading, because descents=[1,3,4] sounds like it should give the permutations with descent composition [1,3,4], but the role of [1,3,4] here is absolutely not that of a composition.

Would you agree with axing the syntax?

[darij]

I'm going out for a walk, but here is a fix for the overly liberal check() method of multiset/set permutations. I have relegated the checking to __contains__; is that OK in terms of coding style?

Note that I have not tested for speed regressions. I fear there might be some.

Also, am I seeing it right that Permutations_set doesn't inherit from Permutations_mset? Is that an issue?

[tscrim]

Replying to darij:

Great!

I'll look into the multisets issue, but as for now here is a fix for another bug:

sage: Permutations(descents=[1,3,4]).list()

gave an error. It turns out that, lacking an n-value in the input, the code would automatically set n to be the maximum entry of the list [1, 3, 4] plus 1 (btw, that causes another bug when the list is empty; fixed as well), but whoever wrote that must have missed the fact that the positions start with 0 (so a presence of 3 in the list really means that the permutations will have a descent at 4, i. e., their value at 4 will be larger than their value at 5), so the "correct" n would be the maximum entry of the list [1, 3, 4] plus 2.

Mmmmm...zero based indexing errors. I completely forgot to fix the containment issue when folding in the review patch. Sorry.

I think this is a completely stupid convention to make, and the syntax (giving the set of descents as a list without the n, having Sage automatically choose the n) should not be supported (no doctests in permutation.py use this syntax). Note that it only allows constructing permutations where the penultimate position is a descent; all the others require the long syntax with the n given! Also, it is misleading, because descents=[1,3,4] sounds like it should give the permutations with descent composition [1,3,4], but the role of [1,3,4] here is absolutely not that of a composition.

I wouldn't think it would be able to handle the descents composition (even without considering the doc which explicitly states this).

Would you agree with axing the syntax?

I'm not opposed to deprecating that form of input (it's not syntax strictly speaking), so if descents is passed in and no n, then it raises a deprecation warning.

I'll be going to sleep now (I'm in India in case you're curious), so you won't get a reply for at least 8 hours from me. Although at this rate I think there won't be a single bug left anywhere near permutations. XP

Thanks,
Travis

[darij]

I've deprecated it now -- but I still wouldn't mind seeing this way of generating permutations removed, seeing that before my fix today it would raise errors the first time one would try to do anything with it (unless the descents list was set to be the empty list)...

Anyway, on to the more interesting parts of the file.

[darij]

review patch. finished!

[darij]

I've done the part of the review I think I was competent enough for. Not covered are:

-- I hope the __classcall_private__ methods are actually doing what they should; while this is likely given the many doctests, I am not making any claims about this because I don't know what the heck _classcall_private__ means to begin with.

-- Same for __setstate__.

-- sage/combinat/set_partition_ordered.py: I'd like you to remove that change and qfold the (IMHO more logical) #14883 into this patch instead (once you've cast an eye on what it does to ensure I did nothing wrong there).

-- A docstring says that __call__ is a close variant of __call__:

    def __call__(self, x):
        """
        A close variant of ``__call__`` which just attempts to extend
        the permutation.

This used to be:

    def __call__(self, x):
        """
        A close variant of CombinatorialClass.__call__ which just
        attempts to extend the permutation

Since you probably understand this better than I do, it's best if you fix this docstring.

-- Speed might be worth testing after I added those __contains__es.

Altogether, great job. If you're fine with my review patch and handle the above five bullet points, feel free to set this to positive review!

Finally, an observation I wish I had made earlier: kdiff3 is much better at deltaing your changes than mercurial...

[tscrim]

Replying to darij:

I've done the part of the review I think I was competent enough for. Not covered are:

-- I hope the __classcall_private__ methods are actually doing what they should; while this is likely given the many doctests, I am not making any claims about this because I don't know what the heck _classcall_private__ means to begin with.

When doing something like Permutation([1,2,3]), what happens is first __classcall_private__() is called which should process the information and return the correct object (it's super function will call the class's __init__() if called). So in the above example, it creates puts the permutation in the correct parent class. For Permutations, it returns the correct parent object based upon the input.

-- Same for __setstate__.

It's used in pickling. This is called when something is trying to be unpickled, ex. loads(dumps(obj)).

-- sage/combinat/set_partition_ordered.py: I'd like you to remove that change and qfold the (IMHO more logical) #14883 into this patch instead (once you've cast an eye on what it does to ensure I did nothing wrong there).

I can't change this back because I have to make it use the correct class (because there is no longer a Permutation_class). I'll review #14883 however.

-- A docstring says that __call__ is a close variant of __call__:

    def __call__(self, x):
        """
        A close variant of ``__call__`` which just attempts to extend
        the permutation.

This used to be:

    def __call__(self, x):
        """
        A close variant of CombinatorialClass.__call__ which just
        attempts to extend the permutation

Since you probably understand this better than I do, it's best if you fix this docstring.

I've tweaked the docstring a bit so that it's more clear.

-- Speed might be worth testing after I added those __contains__es.

Seems okay to me. It's better that it's done correctly anyways.

Altogether, great job. If you're fine with my review patch and handle the above five bullet points, feel free to set this to positive review!

Thank you Darij!

[darij]

Nice! Thanks for the tweaks.

When doing something like Permutation([1,2,3]), what happens is first __classcall_private__() is called which should process the information and return the correct object (it's super function will call the class's __init__() if called). So in the above example, it creates puts the permutation in the correct parent class. For Permutations, it returns the correct parent object based upon the input.

Okay. What is the difference to __classcall__()?

I can't change this back because I have to make it use the correct class (because there is no longer a Permutation_class). I'll review #14883 however.

I'm surprised by the fact that #14883 still applies; since it does, of course, it's better to just leave it separated.

[tscrim]

Replying to darij:

Okay. What is the difference to __classcall__()?

The difference is __classcall_private__() is not inherited (in the sense that it is not called).

[darij]

Ah, I see.

[darij]

Why 5.12? There's currently a ton of stuff depending on this patch, and merging will not become easier just because we wait a few more weeks...

[jferreira]

With this applied to 5.11.rc0:

$ hg qapplied
trac_7983-major_index_and_other_tableau_fixes-dg.patch
trac_7983-review-ts.patch
trac_8386_really_just_moving-fc.patch
trac_8386_big_clean_fc.patch
trac_8386_assert_removal.patch
trac_14516-crystals_speedup-ts.patch
trac_14519-cynthonize_element_wrapper-ts.patch
trac_14808-recoils_of_permutations-ts.patch
trac_14772-remove_cc_permutations-ts.patch

I get a doctest error:

$ sage -t --long /Applications/sage/devel/sage/sage/doctest/sources.py
...
1 item had failures:
   1 of   9 in sage.doctest.sources.FileDocTestSource._test_enough_doctests
    [327 tests, 1 failure, 88.66 s]
----------------------------------------------------------------------
sage -t --long /Applications/sage/devel/sage/sage/doctest/sources.py  # 1 doctest failed
----------------------------------------------------------------------

No error when I qpop trac_14772-remove_cc_permutations-ts.patch

[tscrim]

Fixed. I think I removed a test from the options after I did a check on the sources. Thanks for catching that.

Doctesting 1 file.
sage -t --long ../doctest/sources.py
    [327 tests, 130.57 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 131.0 seconds
    cpu time: 121.6 seconds
    cumulative wall time: 130.6 seconds

For patchbot:

Apply: trac_14772-remove_cc_permutations-ts.patch

[tscrim]

Trivial rebase over #14863.

For patchbot:

Apply: trac_14772-remove_cc_permutations-ts.patch

[zabrocki]

There is something wrong !

Before applying this patch:

sage: Permutation([3,2,1])

After applying this patch:

sage: Permutation([3,2,1])
Traceback (most recent call last)
...
TypeError: __init__() got multiple values for keyword argument 'parent'

How can that be an error (and what does that error message tell me)?

[darij]

Weird, because I'm not getting this error. Can you quote the whole traceback maybe?

[zabrocki]

I'm glad that this is not intentional. I was worried that this patch made more significant changes to the use of the Permutation class.

sage: Permutation([3,2,1])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-1-b3e6779bea6e> in <module>()
----> 1 Permutation([Integer(3),Integer(2),Integer(1)])

/Applications/sage-5.11.rc0/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.so in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (sage/misc/classcall_metaclass.c:1224)()

/Applications/sage-5.11.rc0/local/lib/python2.7/site-packages/sage/combinat/permutation.pyc in __classcall_private__(cls, l, check_input)
    499 
    500         # otherwise, it gets processed by CombinatorialObject's __init__.
--> 501         return Permutations()(l, check_input=check_input)
    502 
    503     def __init__(self, parent, l, check_input=True):

/Applications/sage-5.11.rc0/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8154)()

/Applications/sage-5.11.rc0/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (sage/structure/coerce_maps.c:4278)()

/Applications/sage-5.11.rc0/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (sage/structure/coerce_maps.c:4089)()

/Applications/sage-5.11.rc0/local/lib/python2.7/site-packages/sage/categories/sets_cat.pyc in _element_constructor_from_element_class(self, *args, **keywords)
    337                 17
    338             """
--> 339             return self.element_class(parent = self, *args, **keywords)
    340 
    341         def is_parent_of(self, element):

/Applications/sage-5.11.rc0/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.so in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (sage/misc/classcall_metaclass.c:1243)()

TypeError: __init__() got multiple values for keyword argument 'parent'

[darij]

I think this is because you don't have #14519 applied. Is that so?

[zabrocki]

Yes. That was missing and it seems to work fine. This was my fault. Thanks for helping.