Sage: Ticket #14772: Remove CombinatorialClass from Permutations
https://trac.sagemath.org/ticket/14772
<p>
Part of <a class="new ticket" href="https://trac.sagemath.org/ticket/12913" title="enhancement: Deprecate CombinatorialClass in favor of the EnumeratedSet's categories (new)">#12913</a>.
</p>
<hr />
<p>
Apply: <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14772/trac_14772remove_cc_permutationsts.patch" title="Attachment 'trac_14772remove_cc_permutationsts.patch' in Ticket #14772">trac_14772remove_cc_permutationsts.patch</a><a class="tracrawlink" href="https://trac.sagemath.org/rawattachment/ticket/14772/trac_14772remove_cc_permutationsts.patch" title="Download"></a>
</p>
enusSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14772
Trac 1.1.6tscrimFri, 28 Jun 2013 16:41:05 GMTstatus, cc changed; dependencies set
https://trac.sagemath.org/ticket/14772#comment:1
https://trac.sagemath.org/ticket/14772#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>cc</strong>
<em>nthier</em> added
</li>
<li><strong>dependencies</strong>
set to <em>#8386</em>
</li>
</ul>
<p>
Minor dependency on <a class="closed ticket" href="https://trac.sagemath.org/ticket/8386" title="defect: move iet from sage.combinat to sage.dynamics (closed: fixed)">#8386</a> due to use of <code>Permutation_class</code>.
</p>
TickettscrimSun, 30 Jun 2013 17:16:37 GMTdependencies changed
https://trac.sagemath.org/ticket/14772#comment:2
https://trac.sagemath.org/ticket/14772#comment:2
<ul>
<li><strong>dependencies</strong>
changed from <em>#8386</em> to <em>#8386 #14519</em>
</li>
</ul>
<p>
Let's try it with <a class="closed ticket" href="https://trac.sagemath.org/ticket/14519" title="enhancement: Cythonize ElementWrapper and make parent the first argument (closed: fixed)">#14519</a> as a dependency.
</p>
TicketmhansenMon, 01 Jul 2013 12:42:40 GMT
https://trac.sagemath.org/ticket/14772#comment:3
https://trac.sagemath.org/ticket/14772#comment:3
<p>
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?
</p>
TickettscrimMon, 01 Jul 2013 13:37:48 GMT
https://trac.sagemath.org/ticket/14772#comment:4
https://trac.sagemath.org/ticket/14772#comment:4
<p>
I added some (simple) doctests to the <code>__classcall_private__()</code> functions.
</p>
TickettscrimMon, 01 Jul 2013 13:38:16 GMTcc changed
https://trac.sagemath.org/ticket/14772#comment:5
https://trac.sagemath.org/ticket/14772#comment:5
<ul>
<li><strong>cc</strong>
<em>nthiery</em> added; <em>nthier</em> removed
</li>
</ul>
TicketzabrockiTue, 02 Jul 2013 02:54:08 GMTcc changed
https://trac.sagemath.org/ticket/14772#comment:6
https://trac.sagemath.org/ticket/14772#comment:6
<ul>
<li><strong>cc</strong>
<em>zabrocki</em> added
</li>
</ul>
TickettscrimFri, 12 Jul 2013 05:15:24 GMT
https://trac.sagemath.org/ticket/14772#comment:7
https://trac.sagemath.org/ticket/14772#comment:7
<p>
All doctest errors should be fixed now.
</p>
TicketdarijFri, 12 Jul 2013 17:07:00 GMT
https://trac.sagemath.org/ticket/14772#comment:8
https://trac.sagemath.org/ticket/14772#comment:8
<p>
This conflicts with <a class="closed ticket" href="https://trac.sagemath.org/ticket/14808" title="defect: Permutation([1,2,3,5,4]).recoils_composition() returns [5] instead of ... (closed: fixed)">#14808</a> again. Travis, could you update <a class="closed ticket" href="https://trac.sagemath.org/ticket/14808" title="defect: Permutation([1,2,3,5,4]).recoils_composition() returns [5] instead of ... (closed: fixed)">#14808</a> please? Thank you.
</p>
TickettscrimFri, 12 Jul 2013 19:23:06 GMTdependencies changed
https://trac.sagemath.org/ticket/14772#comment:9
https://trac.sagemath.org/ticket/14772#comment:9
<ul>
<li><strong>dependencies</strong>
changed from <em>#8386 #14519</em> to <em>#8386 #14519 #14808</em>
</li>
</ul>
<p>
I put this over <a class="closed ticket" href="https://trac.sagemath.org/ticket/14808" title="defect: Permutation([1,2,3,5,4]).recoils_composition() returns [5] instead of ... (closed: fixed)">#14808</a>, so I'm putting that as a dependency now.
</p>
TicketdarijFri, 12 Jul 2013 19:33:22 GMT
https://trac.sagemath.org/ticket/14772#comment:10
https://trac.sagemath.org/ticket/14772#comment:10
<p>
It'll probably need some rebase, though.
</p>
TickettscrimFri, 12 Jul 2013 19:49:03 GMT
https://trac.sagemath.org/ticket/14772#comment:11
https://trac.sagemath.org/ticket/14772#comment:11
<p>
I already had <a class="closed ticket" href="https://trac.sagemath.org/ticket/14808" title="defect: Permutation([1,2,3,5,4]).recoils_composition() returns [5] instead of ... (closed: fixed)">#14808</a> applied in the combinat queue, so it shouldn't need rebasing.
</p>
TicketdarijFri, 12 Jul 2013 19:54:07 GMT
https://trac.sagemath.org/ticket/14772#comment:12
https://trac.sagemath.org/ticket/14772#comment:12
<p>
OOPS, you're right. Sorry; I had an obsolete patch in my .hg/patches folder.
</p>
TicketdarijFri, 12 Jul 2013 20:19:38 GMT
https://trac.sagemath.org/ticket/14772#comment:13
https://trac.sagemath.org/ticket/14772#comment:13
<p>
But the <code>number_of_inversions(self)</code> docstring is still unfixed, or am I totally wrong about it?
</p>
TickettscrimSat, 13 Jul 2013 04:25:00 GMT
https://trac.sagemath.org/ticket/14772#comment:14
https://trac.sagemath.org/ticket/14772#comment:14
<div class="wikicode"><div class="code"><pre><span class="gu">@@ 1542,10 +1561,10 @@ class Permutation_class(CombinatorialObj
</span>
def number_of_inversions(self):
r"""
<span class="gd"> 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].
</span><span class="gi">+ 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`.
</span>
REFERENCES:
</pre></div></div>
TicketdarijSat, 13 Jul 2013 08:30:32 GMT
https://trac.sagemath.org/ticket/14772#comment:15
https://trac.sagemath.org/ticket/14772#comment:15
<p>
I wasn't speaking about the syntax. It should say "a pair of elements <code>(i, j)</code>", not "a pair of elements <code>(p_i, p_j)</code>", so as not to confuse the reader about the output of the <code>inversions()</code> method.
</p>
TickettscrimSat, 13 Jul 2013 10:12:15 GMT
https://trac.sagemath.org/ticket/14772#comment:16
https://trac.sagemath.org/ticket/14772#comment:16
<p>
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.
</p>
TickettscrimSat, 13 Jul 2013 13:40:09 GMT
https://trac.sagemath.org/ticket/14772#comment:17
https://trac.sagemath.org/ticket/14772#comment:17
<p>
With the following patches applied on <code>5.11.beta3</code>
</p>
<pre class="wiki">tscrim@as96:~/sage5.11.beta3/devel/sagecombinat/sage/combinat$ sage hg qapplied
trac_14610LSenergyms.patch
trac9107_nesting_nested_classes.patch
trac_9107_fix_cross_reference.patch
trac_13589categoriesc3_under_controlnt.patch
trac_14714_latex_dyckword_fix.patch
trac_14748_deprecationwarning.patch
trac_14748_doctest.patch
trac_14748reviewts.patch
trac_14787gyw_statsbs.patch
trac_14762fix_ASM_nets.patch
trac_12940_affine_permutationstd.patch
trac_14573path_realizationsts.patch
trac_14507tropical_semiringts.patch
trac_11407list_clone_improvefh.patch
trac_14516crystals_speedupts.patch
trac_7983major_index_and_other_tableau_fixesdg.patch
trac_7983reviewts.patch
trac_12882matrix_as_dynkin_diagramts.patch
trac_14722lazy_import_at_startupnt.patch
trac_8386_really_just_movingfc.patch
trac_8386_big_clean_fc.patch
trac_8386_assert_removal.patch
trac_14808recoils_of_permutationsts.patch
trac_10630vector_partitionap.patch
trac_14870fix_int_mod_QQts.patch
trac_14882backtrack_longtimedg.patch
trac_14469_repr_graphics.patch
trac_14519cynthonize_element_wrapperts.patch
trac_12250ktableauxas.patch
trac_14776strongktableauxmz.patch
trac_14772remove_cc_permutationsts.patch
</pre><p>
I cannot reproduce the doctest failure from the patchbot
</p>
<pre class="wiki">tscrim@as96:~/sage5.11.beta3/devel/sagecombinat/sage/combinat$ sage tp long combinat.py
Running doctests with ID 201307131905232a0e8ee8.
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
</pre><p>
Only <a class="closed ticket" href="https://trac.sagemath.org/ticket/12250" title="enhancement: Implementation of weak ktableaux (closed: fixed)">#12250</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/14476" title="defect: nonintegral models can cause a bug in local_data for elliptic curves ... (closed: fixed)">#14476</a> 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...
</p>
TicketdarijSat, 13 Jul 2013 13:53:58 GMT
https://trac.sagemath.org/ticket/14772#comment:18
https://trac.sagemath.org/ticket/14772#comment:18
<p>
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 <a class="missing wiki">FiniteEnumeratedSets?</a> (?) which just takes the length of the list().
</p>
TickettscrimSun, 14 Jul 2013 04:07:20 GMT
https://trac.sagemath.org/ticket/14772#comment:19
https://trac.sagemath.org/ticket/14772#comment:19
<p>
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.
</p>
TickettscrimTue, 16 Jul 2013 10:17:36 GMT
https://trac.sagemath.org/ticket/14772#comment:20
https://trac.sagemath.org/ticket/14772#comment:20
<p>
Mike, do you think you could do a rereview of this patch? Thanks.
</p>
TickettscrimThu, 18 Jul 2013 03:45:10 GMT
https://trac.sagemath.org/ticket/14772#comment:21
https://trac.sagemath.org/ticket/14772#comment:21
<p>
Darij, since Mike hasn't responding, do you think you could do the final review of this patch? Thanks.
</p>
TicketdarijFri, 19 Jul 2013 01:42:56 GMT
https://trac.sagemath.org/ticket/14772#comment:22
https://trac.sagemath.org/ticket/14772#comment:22
<p>
I've started the review  but I'm stuck at <code>PermutationOptions</code> now. You have these doctests:
</p>
<pre class="wiki"> 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')
</pre><p>
But when I try to run them ingame, they don't behave that nicely:
</p>
<pre class="wiki">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)
<ipythoninput49b0a2d723e60c> in <module>()
> 1 po['display']
TypeError: 'NoneType' object has no attribute '__getitem__'
</pre><p>
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.
</p>
TickettscrimFri, 19 Jul 2013 03:11:18 GMT
https://trac.sagemath.org/ticket/14772#comment:23
https://trac.sagemath.org/ticket/14772#comment:23
<p>
Ack...I forgot to check the global options tests. That syntax is from the old sytle, it should be <code></code>Permutations.global_options<code></code>. I'll fix them.
</p>
<p>
You're also correct in that the doctest framework does not pick up dynamically created docstrings (unfortunately).
</p>
<p>
Thanks,<br />
Travis
</p>
TickettscrimFri, 19 Jul 2013 03:28:07 GMT
https://trac.sagemath.org/ticket/14772#comment:24
https://trac.sagemath.org/ticket/14772#comment:24
<p>
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.
</p>
<p>
Best,<br />
Travis
</p>
TickettscrimFri, 19 Jul 2013 04:05:03 GMT
https://trac.sagemath.org/ticket/14772#comment:25
https://trac.sagemath.org/ticket/14772#comment:25
<p>
Okay, here's the new version.
</p>
TicketdarijFri, 19 Jul 2013 11:09:05 GMT
https://trac.sagemath.org/ticket/14772#comment:26
https://trac.sagemath.org/ticket/14772#comment:26
<p>
In case noone disagrees, I'll remove the "like composition of functions" from this:
</p>
<pre class="wiki"> * "l2r"  left to right like composition of functions (p_1 *
p_2)(x) = p_2(p_1(x))
</pre><p>
because it's extremely misleading. Of course, the whole idea of global variables for this is bad, but that's for a later ticket.
</p>
TicketdarijFri, 19 Jul 2013 11:43:13 GMT
https://trac.sagemath.org/ticket/14772#comment:27
https://trac.sagemath.org/ticket/14772#comment:27
<p>
Sorry for the spam but I'll be updating this thread with anything potentially controversial I'm doing in my review patch.
</p>
<p>
The latex method for permutations in reducedword notation returns an empty string when the permutation is id. I'll replace this by a "1".
</p>
TickettscrimFri, 19 Jul 2013 11:46:01 GMT
https://trac.sagemath.org/ticket/14772#comment:28
https://trac.sagemath.org/ticket/14772#comment:28
<p>
How about 'e' or the empty set instead as to avoid potential conflicts? Or better yet, add a global option about that.
</p>
TicketdarijFri, 19 Jul 2013 11:52:51 GMT
https://trac.sagemath.org/ticket/14772#comment:29
https://trac.sagemath.org/ticket/14772#comment:29
<p>
You mean an additional one, or allow several different values for the "latex" option?
</p>
<p>
(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?)
</p>
TickettscrimFri, 19 Jul 2013 11:59:20 GMT
https://trac.sagemath.org/ticket/14772#comment:30
https://trac.sagemath.org/ticket/14772#comment:30
<p>
I mean add 1 additional global option of the form <code>latex_identity_word</code> which will follow the <code>latex_diagram_str</code> global option in <code>partition.py</code>.
</p>
<p>
(I think this pattern leads to more readable code; although it seems to make circular imports more prone to breaking.)
</p>
TicketdarijFri, 19 Jul 2013 14:10:41 GMT
https://trac.sagemath.org/ticket/14772#comment:31
https://trac.sagemath.org/ticket/14772#comment:31
<p>
I've done that change  feel free to comment.
</p>
<p>
In other news, Sage doesn't consider the empty permutation to avoid <code>[1]</code>. Do we consider this a bug? (The chances of being bitten by this are nigh 0.)
</p>
TicketzabrockiFri, 19 Jul 2013 14:16:21 GMT
https://trac.sagemath.org/ticket/14772#comment:32
https://trac.sagemath.org/ticket/14772#comment:32
<p>
Hi Darij, Can you clarify what you mean? <code>Permutation([]).avoids([1])</code> returns <code>True</code> for me. If that were not the case, I would consider that a bug.
</p>
TicketdarijFri, 19 Jul 2013 14:18:31 GMT
https://trac.sagemath.org/ticket/14772#comment:33
https://trac.sagemath.org/ticket/14772#comment:33
<p>
Oh, but:
</p>
<pre class="wiki">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
</pre><p>
I guess this is a backtrack.py issue...
</p>
TicketdarijFri, 19 Jul 2013 14:35:09 GMT
https://trac.sagemath.org/ticket/14772#comment:34
https://trac.sagemath.org/ticket/14772#comment:34
<p>
Should I fix this bug:
</p>
<pre class="wiki">sage: S = Permutations(['c','a'])
sage: elt = S(['c','c','c'])
sage: elt in S
True
</pre><p>
or is it used in some other files to hack around permutations restrictions similarly to how we use(d?) nonstandard permutations?
</p>
TickettscrimFri, 19 Jul 2013 14:45:37 GMT
https://trac.sagemath.org/ticket/14772#comment:35
https://trac.sagemath.org/ticket/14772#comment:35
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14772#comment:34" title="Comment 34">darij</a>:
</p>
<blockquote class="citation">
<p>
Should I fix this bug:
</p>
<pre class="wiki">sage: S = Permutations(['c','a'])
sage: elt = S(['c','c','c'])
sage: elt in S
True
</pre><p>
or is it used in some other files to hack around permutations restrictions similarly to how we use(d?) nonstandard permutations?
</p>
</blockquote>
<p>
I think it should be fixed. I suspect it's something I introduced... (especially in that case)
</p>
<p>
I also can't reproduce the avoidance part:
</p>
<pre class="wiki">sage: [] in Permutations(0, avoiding=[1])
True
sage: [] in Permutations(avoiding=[1])
True
</pre><p>
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.
</p>
TicketdarijFri, 19 Jul 2013 15:04:10 GMT
https://trac.sagemath.org/ticket/14772#comment:36
https://trac.sagemath.org/ticket/14772#comment:36
<p>
I tried this change to the <code>check</code> element method of class <code>Permutations_set</code>:
</p>
<pre class="wiki">@@ 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):
</pre><p>
But this breaks various doctests since apparently the same <code>check</code> method is used for permutations of length k. I have reverted that change for now.
</p>
<p>
If you ask me, it is a stupid idea to have permutations of length k inherit from permutations anyway...
</p>
TickettscrimFri, 19 Jul 2013 16:03:27 GMT
https://trac.sagemath.org/ticket/14772#comment:37
https://trac.sagemath.org/ticket/14772#comment:37
<p>
<code>Permutations</code> 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 <code>__contains__()</code> for the nonstandard permutations, perhaps a stupid <code>return x in list(self)</code> (which, somewhat surprisingly to me, the category of <code>FiniteEnumeratedSets</code> does not provide by default).
</p>
<p>
Also, to fix the backtracker issue, what needs to be done is some simple corner case checking in the <code>__iter__</code> methods for <code>n == 0</code>. Only if <code>n > 0</code> do you call <code>PatternAvoider</code>.
</p>
<p>
Best,<br />
Travis
</p>
TicketdarijFri, 19 Jul 2013 16:12:53 GMT
https://trac.sagemath.org/ticket/14772#comment:38
https://trac.sagemath.org/ticket/14772#comment:38
<p>
I'm getting <code>SyntaxError: 'return' with argument inside generator</code> when I try to fix this. Can you fix that one?
</p>
TicketdarijFri, 19 Jul 2013 16:14:54 GMT
https://trac.sagemath.org/ticket/14772#comment:39
https://trac.sagemath.org/ticket/14772#comment:39
<p>
(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 <span class="underline">check</span> 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'd also love it if you could sketch what changes you have made to the structure; the .patch file is mostly unreadable due to a bad diff encoding algorithm.)
</p>
<p>
I won't return to this ticket in the next 3 or so hours.)
</p>
TickettscrimFri, 19 Jul 2013 16:17:49 GMT
https://trac.sagemath.org/ticket/14772#comment:40
https://trac.sagemath.org/ticket/14772#comment:40
<p>
I can't reupload over your review patch. Is it okay if I just fold it in to the main one?
</p>
TicketdarijFri, 19 Jul 2013 16:19:19 GMT
https://trac.sagemath.org/ticket/14772#comment:41
https://trac.sagemath.org/ticket/14772#comment:41
<p>
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!
</p>
<p>
(The code I commented out  <code>#l[pos_im1] = i1</code> and similar  was just doing nothing.)
</p>
TickettscrimFri, 19 Jul 2013 16:48:04 GMTdescription changed
https://trac.sagemath.org/ticket/14772#comment:42
https://trac.sagemath.org/ticket/14772#comment:42
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14772?action=diff&version=42">diff</a>)
</li>
</ul>
<p>
I hacked around it:
</p>
<pre class="wiki">if n > 0:
return iter(PatternAvoider(self, self._p))
return iter([self.element_class(self, [])])
</pre><p>
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.
</p>
<p>
All combined and back to you Darij.
</p>
TickettscrimFri, 19 Jul 2013 16:48:54 GMT
https://trac.sagemath.org/ticket/14772#comment:43
https://trac.sagemath.org/ticket/14772#comment:43
<p>
For patchbot:
</p>
<p>
Apply: trac_14772remove_cc_permutationsts.patch
</p>
TicketdarijFri, 19 Jul 2013 17:43:24 GMT
https://trac.sagemath.org/ticket/14772#comment:44
https://trac.sagemath.org/ticket/14772#comment:44
<p>
Great!
</p>
<p>
I'll look into the multisets issue, but as for now here is a fix for another bug:
</p>
<pre class="wiki">sage: Permutations(descents=[1,3,4]).list()
</pre><p>
gave an error. It turns out that, lacking an nvalue in the input, the code would automatically set n to be the maximum entry of the list <code>[1, 3, 4]</code> 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 <code>[1, 3, 4]</code> 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 <code>descents=[1,3,4]</code> sounds like it should give the permutations with descent composition <code>[1,3,4]</code>, but the role of <code>[1,3,4]</code> here is absolutely not that of a composition.
</p>
<p>
Would you agree with axing the syntax?
</p>
TicketdarijFri, 19 Jul 2013 18:06:00 GMT
https://trac.sagemath.org/ticket/14772#comment:45
https://trac.sagemath.org/ticket/14772#comment:45
<p>
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 <code>__contains__</code>; is that OK in terms of coding style?
</p>
<p>
Note that I have not tested for speed regressions. I fear there might be some.
</p>
<p>
Also, am I seeing it right that <code>Permutations_set</code> doesn't inherit from <code>Permutations_mset</code>? Is that an issue?
</p>
TickettscrimFri, 19 Jul 2013 18:13:53 GMT
https://trac.sagemath.org/ticket/14772#comment:46
https://trac.sagemath.org/ticket/14772#comment:46
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14772#comment:44" title="Comment 44">darij</a>:
</p>
<blockquote class="citation">
<p>
Great!
</p>
<p>
I'll look into the multisets issue, but as for now here is a fix for another bug:
</p>
<pre class="wiki">sage: Permutations(descents=[1,3,4]).list()
</pre><p>
gave an error. It turns out that, lacking an nvalue in the input, the code would automatically set n to be the maximum entry of the list <code>[1, 3, 4]</code> 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 <code>[1, 3, 4]</code> plus 2.
</p>
</blockquote>
<p>
Mmmmm...zero based indexing errors. I completely forgot to fix the containment issue when folding in the review patch. Sorry.
</p>
<blockquote class="citation">
<p>
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 <code>descents=[1,3,4]</code> sounds like it should give the permutations with descent composition <code>[1,3,4]</code>, but the role of <code>[1,3,4]</code> here is absolutely not that of a composition.
</p>
</blockquote>
<p>
I wouldn't think it would be able to handle the descents composition (even without considering the doc which explicitly states this).
</p>
<blockquote class="citation">
<p>
Would you agree with axing the syntax?
</p>
</blockquote>
<blockquote>
<p>
I'm not opposed to deprecating that form of input (it's not syntax strictly speaking), so if <code>descents</code> is passed in and no <code>n</code>, then it raises a deprecation warning.
</p>
</blockquote>
<p>
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
</p>
<p>
Thanks,<br />
Travis
</p>
TicketdarijFri, 19 Jul 2013 21:32:52 GMT
https://trac.sagemath.org/ticket/14772#comment:47
https://trac.sagemath.org/ticket/14772#comment:47
<p>
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)...
</p>
<p>
Anyway, on to the more interesting parts of the file.
</p>
TicketdarijFri, 19 Jul 2013 23:21:53 GMTattachment set
https://trac.sagemath.org/ticket/14772
https://trac.sagemath.org/ticket/14772
<ul>
<li><strong>attachment</strong>
set to <em>trac_14772reviewdg.patch</em>
</li>
</ul>
<p>
review patch. finished!
</p>
TicketdarijFri, 19 Jul 2013 23:35:36 GMT
https://trac.sagemath.org/ticket/14772#comment:48
https://trac.sagemath.org/ticket/14772#comment:48
<p>
I've done the part of the review I think I was competent enough for. Not covered are:
</p>
<p>
 I hope the <code>__classcall_private__</code> 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 <code>_classcall_private__</code> means to begin with.
</p>
<p>
 Same for <code>__setstate__</code>.
</p>
<p>
 <code>sage/combinat/set_partition_ordered.py</code>: I'd like you to remove that change and qfold the (IMHO more logical) <a class="closed ticket" href="https://trac.sagemath.org/ticket/14883" title="defect: Weird multiplication by identity in set_partition_ordered.py (closed: fixed)">#14883</a> into this patch instead (once you've cast an eye on what it does to ensure I did nothing wrong there).
</p>
<p>
 A docstring says that <code>__call__</code> is a close variant of <code>__call__</code>:
</p>
<pre class="wiki"> def __call__(self, x):
"""
A close variant of ``__call__`` which just attempts to extend
the permutation.
</pre><p>
This used to be:
</p>
<pre class="wiki"> def __call__(self, x):
"""
A close variant of CombinatorialClass.__call__ which just
attempts to extend the permutation
</pre><p>
Since you probably understand this better than I do, it's best if you fix this docstring.
</p>
<p>
 Speed might be worth testing after I added those <code>__contains__</code>es.
</p>
<p>
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!
</p>
<p>
Finally, an observation I wish I had made earlier: kdiff3 is much better at deltaing your changes than mercurial...
</p>
TickettscrimSat, 20 Jul 2013 04:59:09 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/14772#comment:49
https://trac.sagemath.org/ticket/14772#comment:49
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Mike Hansen, Darij Grinberg</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14772#comment:48" title="Comment 48">darij</a>:
</p>
<blockquote class="citation">
<p>
I've done the part of the review I think I was competent enough for. Not covered are:
</p>
<p>
 I hope the <code>__classcall_private__</code> 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 <code>_classcall_private__</code> means to begin with.
</p>
</blockquote>
<p>
When doing something like <code>Permutation([1,2,3])</code>, what happens is first <code>__classcall_private__()</code> is called which should process the information and return the correct object (it's super function will call the class's <code>__init__()</code> if called). So in the above example, it creates puts the permutation in the correct parent class. For <code>Permutations</code>, it returns the correct parent object based upon the input.
</p>
<blockquote class="citation">
<p>
 Same for <code>__setstate__</code>.
</p>
</blockquote>
<p>
It's used in pickling. This is called when something is trying to be unpickled, ex. <code>loads(dumps(obj))</code>.
</p>
<blockquote class="citation">
<p>
 <code>sage/combinat/set_partition_ordered.py</code>: I'd like you to remove that change and qfold the (IMHO more logical) <a class="closed ticket" href="https://trac.sagemath.org/ticket/14883" title="defect: Weird multiplication by identity in set_partition_ordered.py (closed: fixed)">#14883</a> into this patch instead (once you've cast an eye on what it does to ensure I did nothing wrong there).
</p>
</blockquote>
<p>
I can't change this back because I have to make it use the correct class (because there is no longer a <code>Permutation_class</code>). I'll review <a class="closed ticket" href="https://trac.sagemath.org/ticket/14883" title="defect: Weird multiplication by identity in set_partition_ordered.py (closed: fixed)">#14883</a> however.
</p>
<blockquote class="citation">
<p>
 A docstring says that <code>__call__</code> is a close variant of <code>__call__</code>:
</p>
<pre class="wiki"> def __call__(self, x):
"""
A close variant of ``__call__`` which just attempts to extend
the permutation.
</pre><p>
This used to be:
</p>
<pre class="wiki"> def __call__(self, x):
"""
A close variant of CombinatorialClass.__call__ which just
attempts to extend the permutation
</pre><p>
Since you probably understand this better than I do, it's best if you fix this docstring.
</p>
</blockquote>
<p>
I've tweaked the docstring a bit so that it's more clear.
</p>
<blockquote class="citation">
<p>
 Speed might be worth testing after I added those <code>__contains__</code>es.
</p>
</blockquote>
<p>
Seems okay to me. It's better that it's done correctly anyways.
</p>
<blockquote class="citation">
<p>
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!
</p>
</blockquote>
<p>
Thank you Darij!
</p>
TicketdarijSat, 20 Jul 2013 09:07:02 GMT
https://trac.sagemath.org/ticket/14772#comment:50
https://trac.sagemath.org/ticket/14772#comment:50
<p>
Nice! Thanks for the tweaks.
</p>
<blockquote class="citation">
<p>
When doing something like <code>Permutation([1,2,3])</code>, what happens is first <code>__classcall_private__()</code> is called which should process the information and return the correct object (it's super function will call the class's <code>__init__()</code> if called). So in the above example, it creates puts the permutation in the correct parent class. For <code>Permutations</code>, it returns the correct parent object based upon the input.
</p>
</blockquote>
<p>
Okay. What is the difference to <code>__classcall__()</code>?
</p>
<blockquote class="citation">
<p>
I can't change this back because I have to make it use the correct class (because there is no longer a <code>Permutation_class</code>). I'll review <a class="closed ticket" href="https://trac.sagemath.org/ticket/14883" title="defect: Weird multiplication by identity in set_partition_ordered.py (closed: fixed)">#14883</a> however.
</p>
</blockquote>
<p>
I'm surprised by the fact that <a class="closed ticket" href="https://trac.sagemath.org/ticket/14883" title="defect: Weird multiplication by identity in set_partition_ordered.py (closed: fixed)">#14883</a> still applies; since it does, of course, it's better to just leave it separated.
</p>
TickettscrimSat, 20 Jul 2013 09:12:24 GMT
https://trac.sagemath.org/ticket/14772#comment:51
https://trac.sagemath.org/ticket/14772#comment:51
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14772#comment:50" title="Comment 50">darij</a>:
</p>
<blockquote class="citation">
<p>
Okay. What is the difference to <code>__classcall__()</code>?
</p>
</blockquote>
<p>
The difference is <code>__classcall_private__()</code> is not inherited (in the sense that it is not called).
</p>
TicketdarijSat, 20 Jul 2013 09:32:25 GMT
https://trac.sagemath.org/ticket/14772#comment:52
https://trac.sagemath.org/ticket/14772#comment:52
<p>
Ah, I see.
</p>
TicketjdemeyerSun, 21 Jul 2013 21:09:53 GMTmilestone changed
https://trac.sagemath.org/ticket/14772#comment:53
https://trac.sagemath.org/ticket/14772#comment:53
<ul>
<li><strong>milestone</strong>
changed from <em>sage5.11</em> to <em>sage5.12</em>
</li>
</ul>
TicketdarijSun, 21 Jul 2013 21:13:37 GMT
https://trac.sagemath.org/ticket/14772#comment:54
https://trac.sagemath.org/ticket/14772#comment:54
<p>
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...
</p>
TicketjdemeyerFri, 02 Aug 2013 14:47:13 GMTdependencies, milestone changed
https://trac.sagemath.org/ticket/14772#comment:55
https://trac.sagemath.org/ticket/14772#comment:55
<ul>
<li><strong>dependencies</strong>
changed from <em>#8386 #14519 #14808</em> to <em>#8386 #14519 #14808 #14143 #14015 #14516</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage5.12</em> to <em>sagepending</em>
</li>
</ul>
TicketjferreiraWed, 07 Aug 2013 22:31:51 GMTstatus changed
https://trac.sagemath.org/ticket/14772#comment:56
https://trac.sagemath.org/ticket/14772#comment:56
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
With this applied to 5.11.rc0:
</p>
<pre class="wiki">$ hg qapplied
trac_7983major_index_and_other_tableau_fixesdg.patch
trac_7983reviewts.patch
trac_8386_really_just_movingfc.patch
trac_8386_big_clean_fc.patch
trac_8386_assert_removal.patch
trac_14516crystals_speedupts.patch
trac_14519cynthonize_element_wrapperts.patch
trac_14808recoils_of_permutationsts.patch
trac_14772remove_cc_permutationsts.patch
</pre><p>
I get a doctest error:
</p>
<pre class="wiki">$ 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

</pre><p>
No error when I <code>qpop</code> trac_14772remove_cc_permutationsts.patch
</p>
TickettscrimWed, 07 Aug 2013 23:20:14 GMTstatus, reviewer, milestone changed
https://trac.sagemath.org/ticket/14772#comment:57
https://trac.sagemath.org/ticket/14772#comment:57
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Mike Hansen, Darij Grinberg</em> to <em>Mike Hansen, Darij Grinberg, Jeff Ferreira</em>
</li>
<li><strong>milestone</strong>
changed from <em>sagepending</em> to <em>sage5.12</em>
</li>
</ul>
<p>
Fixed. I think I removed a test from the options after I did a check on the sources. Thanks for catching that.
</p>
<pre class="wiki">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
</pre><p>
For patchbot:
</p>
<p>
Apply: trac_14772remove_cc_permutationsts.patch
</p>
TickettscrimFri, 16 Aug 2013 18:41:19 GMTattachment set
https://trac.sagemath.org/ticket/14772
https://trac.sagemath.org/ticket/14772
<ul>
<li><strong>attachment</strong>
set to <em>trac_14772remove_cc_permutationsts.patch</em>
</li>
</ul>
TickettscrimFri, 16 Aug 2013 18:42:03 GMTdependencies changed
https://trac.sagemath.org/ticket/14772#comment:58
https://trac.sagemath.org/ticket/14772#comment:58
<ul>
<li><strong>dependencies</strong>
changed from <em>#8386 #14519 #14808 #14143 #14015 #14516</em> to <em>#8386 #14519 #14808 #14143 #14015 #14516 #14863</em>
</li>
</ul>
<p>
Trivial rebase over <a class="closed ticket" href="https://trac.sagemath.org/ticket/14863" title="defect: permutation from major code returns the wrong permutation for the ... (closed: fixed)">#14863</a>.
</p>
<p>
For patchbot:
</p>
<p>
Apply: trac_14772remove_cc_permutationsts.patch
</p>
TicketzabrockiMon, 19 Aug 2013 12:04:23 GMTstatus changed
https://trac.sagemath.org/ticket/14772#comment:59
https://trac.sagemath.org/ticket/14772#comment:59
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
There is something wrong !
</p>
<p>
Before applying this patch:
</p>
<pre class="wiki">sage: Permutation([3,2,1])
</pre><p>
After applying this patch:
</p>
<pre class="wiki">sage: Permutation([3,2,1])
Traceback (most recent call last)
...
TypeError: __init__() got multiple values for keyword argument 'parent'
</pre><p>
How can that be an error (and what does that error message tell me)?
</p>
TicketdarijMon, 19 Aug 2013 12:42:15 GMT
https://trac.sagemath.org/ticket/14772#comment:60
https://trac.sagemath.org/ticket/14772#comment:60
<p>
Weird, because I'm not getting this error. Can you quote the whole traceback maybe?
</p>
TicketzabrockiMon, 19 Aug 2013 12:45:33 GMT
https://trac.sagemath.org/ticket/14772#comment:61
https://trac.sagemath.org/ticket/14772#comment:61
<p>
I'm glad that this is not intentional. I was worried that this patch made more significant changes to the use of the <code>Permutation</code> class.
</p>
<pre class="wiki">sage: Permutation([3,2,1])

TypeError Traceback (most recent call last)
<ipythoninput1b3e6779bea6e> in <module>()
> 1 Permutation([Integer(3),Integer(2),Integer(1)])
/Applications/sage5.11.rc0/local/lib/python2.7/sitepackages/sage/misc/classcall_metaclass.so in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (sage/misc/classcall_metaclass.c:1224)()
/Applications/sage5.11.rc0/local/lib/python2.7/sitepackages/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/sage5.11.rc0/local/lib/python2.7/sitepackages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8154)()
/Applications/sage5.11.rc0/local/lib/python2.7/sitepackages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (sage/structure/coerce_maps.c:4278)()
/Applications/sage5.11.rc0/local/lib/python2.7/sitepackages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (sage/structure/coerce_maps.c:4089)()
/Applications/sage5.11.rc0/local/lib/python2.7/sitepackages/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/sage5.11.rc0/local/lib/python2.7/sitepackages/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'
</pre>
TicketdarijMon, 19 Aug 2013 12:49:03 GMT
https://trac.sagemath.org/ticket/14772#comment:62
https://trac.sagemath.org/ticket/14772#comment:62
<p>
I think this is because you don't have <a class="closed ticket" href="https://trac.sagemath.org/ticket/14519" title="enhancement: Cythonize ElementWrapper and make parent the first argument (closed: fixed)">#14519</a> applied. Is that so?
</p>
TicketzabrockiMon, 19 Aug 2013 13:08:54 GMTstatus changed
https://trac.sagemath.org/ticket/14772#comment:63
https://trac.sagemath.org/ticket/14772#comment:63
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
Yes. That was missing and it seems to work fine. This was my fault. Thanks for helping.
</p>
TicketjdemeyerTue, 20 Aug 2013 12:56:23 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/14772#comment:64
https://trac.sagemath.org/ticket/14772#comment:64
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage5.12.beta3</em>
</li>
</ul>
Ticket